pat1068 1068 Find More Coins （30 分）

位址:https://pintia.cn/problem-sets/994805342720868352/problems/994805402305150976

利用01背包求解，體積與價值都設為對應的錢币值，因為同時存在多個時，需要輸出最小的，是以将錢币數按從大到小的順序進行排序，用flag[i][j]代表第i個錢币對于加和為j是否被選，如果被選，那麼是true，沒有被選，就是false；如果求出的dp[m] != m,那麼沒有解法，否則輸出即可；

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int MAXN = 1e4 + 5;

int n,m;
int dp[MAXN],num[MAXN];
bool flag[MAXN][105];

bool cmp(const int &p,const int &q){
    return p > q;
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i = 1;i <= n;++i){
        scanf("%d",&num[i]);
    }
    sort(num + 1,num + n + 1,cmp);
    memset(flag, false,sizeof(flag));
    dp[0] = 0;
    for(int i = 1;i <= m;++i){
        dp[i] = -inf;
    }
    for(int i = 1;i <= n;++i){
        for(int j = m;j >= num[i];--j){
            if(dp[j] <= dp[j - num[i]] + num[i]){
                dp[j] = dp[j - num[i]] + num[i];
                flag[i][j] = true;
            }
        }
    }
    if(dp[m] != m) printf("No Solution\n");
    else{
        vector<int>ve;
        int v = m,index = n;
        while(v > 0){
            if(flag[index][v] == true){
                ve.pb(num[index]);
                v -= num[index];
            }
            index--;
        }
        int len = ve.size();
        for(int i = 0;i < len;++i){
            if(i == len - 1){
                printf("%d\n",ve[i]);
            }else{
                printf("%d ",ve[i]);
            }
        }
    }
    return 0;
}