0.2s Java选手卡时间了 C++是真的快。。

思路

1. 先求背包状态，再判断是否有解，有则逆推方案序列
2. $f(i,j)$表示“只考虑前$i$个硬币且总价值恰好为$j$的选法集合”，属性：总价值$Max$
   • 01背包状态计算：$f(i,j) = max(f(i-1,j), f(i-1,j-v)+w)$
3. 逆推就是按$N \sim 1$枚举每个$v_i$，若满足$f(i,j) = f(i-1,j-v_i)+w$，证明当前$v_i$可选，然后更新$j = j - v_i$
4. 要求字典序最小，因此先存硬币面额到数组再降序排列，从而保证逆序时得到的是升序的方案序列
5. 初始值$f(0,0)=0$，集合含义是“恰好”，所以其它状态置为负无穷或一个极小数；若含义改为“不超过”，可直接省去初始化操作，使用默认值0即可，其他代码不变

代码

#include<iostream>
#include<algorithm>

using namespace std;

int n, m, f[10010][110], a[10010];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];  // 硬币面值存到数组
    sort(a+1, a+n+1, [](int a, int b){return a > b;});  // 降序排列

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++) 
            f[i][j] = -9999;   // 初始值 极小数  memset也行
    f[0][0] = 0;  // 不考虑任何数且总和恰好为0的选法 其总和为0

    // 01背包求“只考虑前i个数且总和恰好为j时的最大总和” 很多余 反正就是把总和记到f[i][j]里
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            f[i][j] = f[i-1][j];
            if (j >= a[i]) f[i][j] = max(f[i][j], f[i-1][j-a[i]] + a[i]);
        }
    }

    if (f[n][m] != m) {  // 无解
        cout << "No Solution";
        return 0;
    }
    // a[i]是降序的 逆序遍历保证找到的解法序列字典序最小
    int pos = m;
    for (int i = n; i >= 1 && pos > 0; i--) {
        // 如果当前a[i]可选 且01背包在计算时已选 输出a[i]并更新pos
        if (pos >= a[i] && f[i][pos] == f[i-1][pos-a[i]] + a[i]) {
            cout << a[i] << " ";
            pos -= a[i];
        }
    }
    cout << endl;
    return 0;
}