PATA1068 硬币问题

链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805402305150976

程序代码：

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
/*
    该题需要好好掌握思想，如何将恰好问题转换为背包问题
    以及倒序追踪法，求的序列结果
*/
using namespace std;

const int maxn = 10010;
const int maxm = 110;
int w[maxn],dp[maxm];
bool choice[maxn][maxm];
bool flag[maxn];

int cmp(int a,int b){
    return a > b;
}

int main(int argc, char const *argv[])
{
    int n,M;
    scanf("%d%d",&n,&M);
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    //为了保证输出结果按字典顺序排列，将硬币价格倒序
    sort(w + 1,w + n + 1,cmp);
    //初始阶段
    for(int v=0;v<=M;v++)
        dp[v] = 0;
    //n个阶段
    for(int i=1;i<=n;i++){
        //逆序dp
        for(int v=M;v>=w[i];v--){
            //注意加上等号：因为需按字典顺序向下更新
            if(dp[v] <= dp[v-w[i]] + w[i]){
                dp[v] = dp[v-w[i]] + w[i];
                choice[i][v] = true;
            }else{
                choice[i][v] = false;
            }
        }
    }
    //找到最后一阶段中最大的dp
    int v = 0;
    for(int i=1;i<=M;i++){
        if(dp[i] > dp[v])
            v = i;
    }
    if(dp[v] != M){
        //不能恰好组成M
        printf("No Solution\n");
        return 0;
    }
    //倒序追踪法寻找完整序列
    // printf("max:%d\n",dp[v] );
    std::vector<int> result;
    for(int i=n;i>=1;i--){
        if(choice[i][v] == true){
            // flag[i] = true;
            //更新i-1阶段的状态
            result.push_back(w[i]);
            v = v - w[i];
        }
    }
    for(int i=0;i<result.size();i++){
        printf("%d",result[i] );
        if(i != result.size() - 1)
            printf(" ");
    }
    return 0 ;
    //
}