【CCCC】L3-001 凑零钱 (30分)，01背包路径打印

problem

L3-001 凑零钱 (30分)
韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里，发现这家店有个特别的规矩：你可以用任何星球的硬币付钱，但是绝不找零，当然也不能欠债。韩梅梅手边有 10
​4
​​ 枚来自各个星球的硬币，需要请你帮她盘算一下，是否可能精确凑出要付的款额。

输入格式：
输入第一行给出两个正整数：N（≤10
​4
​​ ）是硬币的总个数，M（≤10
​2
​​ ）是韩梅梅要付的款额。第二行给出 N 枚硬币的正整数面值。数字间以空格分隔。

输出格式：
在一行中输出硬币的面值 V
​1
​​ ≤V
​2
​​ ≤⋯≤V
​k
​​ ，满足条件 V
​1
​​ +V
​2
​​ +...+V
​k
​​ =M。数字间以 1 个空格分隔，行首尾不得有多余空格。若解不唯一，则输出最小序列。若无解，则输出 No Solution。

注：我们说序列{ A[1],A[2],⋯ }比{ B[1],B[2],⋯ }“小”，是指存在 k≥1 使得 A[i]=B[i] 对所有 i<k 成立，并且 A[k]<B[k]。

输入样例 1：
8 9
5 9 8 7 2 3 4 1
输出样例 1：
1 3 5
输入样例 2：
4 8
7 2 4 3
输出样例 2：
No Solution

• 给出n（1e4）种不同面额的硬币
• 恰好凑出m元，并且输出字典序最小的。

solution

• 一种是搜索做法。注意特殊数据所有硬币无法凑出m元要特判。
• 另一种是01背包记录路径（降序 == 最小字典序，反之最大），容量m，代价vi，价值vi, 判断填满容量m的最大价值是否为m。
• 即便相同硬币不止一个，我们也不采用多重背包的方式，把每一个1硬币当成一个独立的单位来进行01背包

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;//RE3,4
const int maxm = 110;
int v[maxn], dp[maxm], pre[maxn][maxm];
bool cmp(int a, int b){return a>b;}
int main(){
    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
        cin>>v[i];
    sort(v+1,v+n+1,cmp);//结论：降序排序=最小字典序
    for(int i = 1; i <= n; i++){
        for(int j = m; j >= v[i]; j--){
            if(dp[j]<=dp[j-v[i]]+v[i]){
                dp[j]=dp[j-v[i]]+v[i]; //选择的代价为v[i],价值为v[i]
                pre[i][j] = 1;//选择了硬币i，标记当前背包位置，记录路径
            }
        }
    }
    if(dp[m]!=m){//容量为m（面额）的背包能获得的最大价值为m。。
        cout<<"No Solution"<<endl;
        return 0;
    }
    //路径打印
    int ok = 0;
    for(int i=n, j=m; i>=1 && j>=0; i--){//注意顺序必须是逆序，和前面相反
        if(pre[i][j]){
            if(!ok){cout<<v[i];ok=1;}
            else cout<<" "<<v[i];
            j -= v[i];//当第i个硬币选中，剩余价值-=vi[i]；
        }
    }
    return 0;
}