1068 Find More Coins (30 分)

题目传送门：1068 Find More Coins (30 分)

一、题目大意

给定n个硬币，求组成m的硬币的最小字典序组合

二、解题思路

背包问题。刚开始没想到什么好的思路，参考了这篇博客：1068 Find More Coins （30 分）背包问题

三、AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n, m;
	vector<int>coin;
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;
		coin.push_back(x);
	}
	sort(coin.begin(), coin.end(), [](int a, int b)->bool{return a > b;});
	vector<int>dp(m+1);
	vector<bool>check[n];
	for(int i = 0; i < n; i++){
		check[i].resize(m+1);
	}
	for(int i = 0; i < n; i++){
		for(int j = m; j >= coin[i]; j--){
			if(dp[j] <= dp[j - coin[i]] + coin[i]){
				dp[j] = dp[j - coin[i]] + coin[i];
				check[i][j] = true;
			}
		}
	}
	if(dp[m] != m){
		cout << "No Solution" << endl;
	}else{
		vector<int>res;
		int i = n-1, j = m;
		while(j > 0){
			if(check[i][j]==true){
				j -= coin[i];
				res.push_back(coin[i]);
			}
			i--;
		}
		for(int i = 0; i < res.size(); i++){
			if(i)cout << " " << res[i];
			else cout << res[i];
		}
		cout << endl;
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
 

文章来源: blog.csdn.net，作者：爱玲姐姐，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jal517486222/article/details/100088832