题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805402305150976
题意：
n个硬币，每一个有一个特有的价值，一个硬币只有一个，要求选取一些硬币使得他们的价值刚好是m
输出字典序最小的方案。
思路：
最近好久没有刷题了连PAT都好久没动了这样不行啊。连背包都有点不大会了。赶紧把PAT30分的刷完去刷洛谷了。
硬币是一个weight和value相同的物品，背包的容量就是m
问题转换成尽量让包中的价值大，背包中的最大价值都无法到达m说明没有答案。
价值是不可能超过m的，因为weight和value相同，weight限制了。
用一个bool二维数组来保存某一个方案中有没有这个硬币。
因为要求输出字典序最小的方案，所以刚开始先从大到小来排序，先考察大的，当小的和当前价值一样的时候也进行更新。
这时候的更新就是将更小的一个方案进行更新。
在逆序跑bool数组存方案就行了。
#include<cstdio>
#include<cstdlib>
#include<map>
#include<set>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stack>
#include<queue> #define inf 0x7fffffff
using namespace std;
typedef long long LL;
typedef pair<string, string> pr; int n, m;
const int maxn = 1e4 + ;
int val[maxn];
bool choice[maxn][];
int dp[maxn]; bool cmp(int a, int b){
return a > b;
} int main()
{
scanf("%d%d", &n, &m);
for(int i = ; i < n; i++){
scanf("%d", &val[i]);
}
sort(val, val + n, cmp);
for(int i = ; i < n; i++){
for(int j = m; j >= val[i]; j--){
if(dp[j] <= dp[j - val[i]] + val[i]){
choice[i][j] = true;
dp[j] = dp[j - val[i]] + val[i];
}
}
}
if(dp[m] != m)printf("No Solution\n");
else{
vector<int>ans;
int now = m, id = n - ;
while(now > ){
if(choice[id][now]){
ans.push_back(val[id]);
now -= val[id];
}
id--;
}
printf("%d", ans[]);
for(int i = ; i < ans.size(); i++){
printf(" %d", ans[i]);
}
printf("\n");
}
return ;
}