题目重述

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

输入格式：

输入第一行给出两个正整数： N ( ≤ 1 0 4 ) N(≤10^4) N(≤104)是硬币的总个数， M ( ≤ 1 0 2 ) M(≤10^2) M(≤102)是韩梅梅要付的款额。第二行给出 N 枚硬币的正整数面值。数字间以空格分隔。

输出格式：

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

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

思路

凑零钱，经典的0-1背包问题，不做赘述。
记录字典序最小的方案直接使用vector的比较运算符， p a t h [ i ] path[i] path[i]表示凑够 i 块钱时字典序最小的方案，题目中m的范围较小，若数据大的话这种方法很可能会T掉，因为vector之间的比较、等号赋值和push_back操作还是比较慢的
记得先对零钱排个序

#include<bits/stdc++.h>
using namespace std;
const int maxn = 105, N = 1e4 + 5;
bool dp[maxn];
vector<vector<int>> path;
int a[N];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    dp[0] = true;
    path.resize(m + 1);
    for (int i = 0; i < n; i++) {
        for (int j = m; j >= a[i]; j--) {
            if (dp[j - a[i]]) {
                if (dp[j]) {
                    vector<int> tmp = path[j - a[i]];
                    tmp.push_back(a[i]);
                    if (tmp < path[j]) path[j] = tmp;
                }
                else {
                    dp[j] = true;
                    path[j] = path[j - a[i]];
                    path[j].push_back(a[i]);
                }
            }
        }
    }
    if (!dp[m]) cout << "No Solution" << endl;
    else for (int i = 0; i < path[m].size(); i++) {
        cout << path[m][i];
        if(i != path[m].size() - 1) cout << " ";
    }
    return 0;
}