PAT甲级1068 Find More Coins【01背包】

题目：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 + 5; 
int val[maxn];
bool choice[maxn][105];
int dp[maxn];
 
bool cmp(int a, int b){
    return a > b;
}
 
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++){
        scanf("%d", &val[i]);
    }
    sort(val, val + n, cmp);
    for(int i = 0; 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 - 1;
        while(now > 0){
            if(choice[id][now]){
                ans.push_back(val[id]);
                now -= val[id];
            }
            id--;
        }
        printf("%d", ans[0]);
        for(int i = 1; i < ans.size(); i++){
            printf(" %d", ans[i]);
        }
        printf("\n"); 
    }
    return 0;
}