凑零钱
韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里，发现这家店有个特别的规矩：你可以用任何星球的硬币付钱，但是绝不找零，当然也不能欠债。韩梅梅手边有 10 4 枚来自各个星球的硬币，需要请你帮她盘算一下，是否可能精确凑出要付的款额。
【输入格式】
输入第一行给出两个正整数：N（≤104 ）是硬币的总个数，M（≤102 ）是韩梅梅要付的款额。第二行给出 N 枚硬币的正整数面值。数字间以空格分隔。
【输出格式】
在一行中输出硬币的面值 V1≤V2 ≤⋯≤Vk ，满足条件 V1 +V2 +...+Vk =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
https://blog.csdn.net/weixin_40163242/article/details/88370029
/*
dp版本
状态：前k个硬币，手上金钱数为cur
实际上就成了一个背包问题
*/
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 10002;
int n, m;
int a[maxn];
int dp[maxn][maxn]; //状态是由dfs的参数推导出来的，因为dfs中有大量重叠子问题
//所以我应该用一个二维dp表来存放这个结果！
int s[maxn][maxn];
vector<int> res;
bool flag = false;
void DP()
{
//前一个硬币
dp[1][a[1]] = 1; //只能凑成a[1]元
s[1][a[1]] = a[1]; //拿自己凑成的
//else
int index = 0;
for(int i = 2;i <= n;i++) //前i个硬币
{
for(int j = 1;j <= m;j++) //手上可能的金额数
{
if(dp[i - 1][j - a[i]] == 1) //因为要顺序最小，所以优先取
{
dp[i][j] = 1;
s[i][j] = a[i]; //取了自己
}
else if(dp[i - 1][j] == 1)
{
dp[i][j] = 1;
s[i][j] = 0; //表示这一步没有取
}
else
{
dp[i][j] = 0; //无法凑成
s[i][j] = 0; //就不取
}
}
if(dp[i][m] == 1)
{
index = i;
flag = true;
break;
}
}
if(flag)
{
//存下路径
int col = m; //价钱
for(int i = index;i >= 1;i--)
{
int coin = s[i][col];
res.push_back(coin);
col = col - coin;
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
cin >> a[i];
}
sort(a + 1, a + 1 + n);
DP();
if(flag)
{
cout << res[res.size() - 1];
for(int i = res.size() - 2;i >= 0;i--)
{
if(res[i] != 0)
cout << " " << res[i];
}
cout << endl;
}
else
cout << "No Solution" << endl;
return 0;
}