浙大PAT CCCC L3-001 凑零钱 ( 0/1背包 && 路径记录 )

题目链接

分析 :

就是一个 0/1 背包，但是需要记录具体状态的转移情况

这个可以想象成一个状态转移图，然后实际就是记录路径

将状态看成点然后转移看成边，最后输出字典序最小的路径

这里有一个很巧妙的做法

先将所有的硬币升序排序（这一点很重要）

然后在这一条件下，假设当前状态是考虑第 i 个硬币，前一个状态是考虑第 i-1 个硬币

试想对于同一个体积，如果选用的硬币数量越多是不是字典序更小

然后对于如果对于同一体积下，选用硬币数一样多的两种方案

由于我们已经升序排序，如果有一样多硬币的情况，那么永远选后面面值大的更新答案

因为体积固定嘛，那么后面选用的硬币面值更大，凑成一样的体积，是不是说明

其他的选用硬币应该更小，也就是字典序更小了？

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 10;
const int INF = 0x3f3f3f3f;
struct Status{ int Coin, Pre; }st[maxn];///记录状态
int dp[maxn], Coin[maxn];
int N, M;

int main(void)
{
    while(~scanf("%d %d", &N, &M)){
        for(int i=0; i<N; i++)
            scanf("%d", &Coin[i]);

        sort(Coin, Coin+N);

        for(int i=0; i<=M; i++)
            st[i].Coin = st[i].Pre = -1,
            dp[i] = -INF;///初始化为负无穷小，对于背包是否刚刚好装满
                         ///一般都选择这样初始化

        dp[0] = 0;
        for(int i=0; i<N; i++){
            for(int j=M; j>=Coin[i]; j--){
                if(dp[j - Coin[i]] + 1 >= dp[j]){///对于 == 的情况，可以去用题目给的第一个样例，
                                                 ///然后去掉这个等号输出答案，再想一下为什么错了，可能理解就更多了
                    dp[j] = dp[j - Coin[i]] + 1;
                    st[j].Coin = Coin[i];///记录当前状态是选了哪个硬币
                    st[j].Pre = j - Coin[i];///记录从哪个状态转移过来
                }
            }
        }

        if(dp[M] > 0){
            vector<int> ans;
            int now = M;
            while(st[now].Coin != -1){///倒序回复路径
                ans.push_back(st[now].Coin);
                now = st[now].Pre;
            }
            for(int i=ans.size()-1; i>=0; i--){///倒序输出倒序路径就是正确路径了
                printf("%d", ans[i]);
                if(i != 0) putchar(' ');
            }puts("");
        }else puts("No Solution");
    }
    return 0;
}