7-1 凑零钱 (30分)
韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里，发现这家店有个特别的规矩：你可以用任何星球的硬币付钱，但是绝不找零，当然也不能欠债。韩梅梅手边有 10^4 枚来自各个星球的硬币，需要请你帮她盘算一下，是否可能精确凑出要付的款额。
输入格式：
输入第一行给出两个正整数：N（≤10^4 ）是硬币的总个数，M（≤10^2 ）是韩梅梅要付的款额。第二行给出 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
题解
动态规划，先对硬币价值升序排序，从左向右依次选取硬币，对于每个硬币都有两种情况，取或不取，当所取硬币总额等于所需总额时，输出，以此进行递归。
对硬币面值排序后，用dfs函数来判断是否取这枚硬币
伪代码
void dfs(int 面值的位置, int 需求硬币数量, int 当前面值和)
{
if (当前的钱加上剩下所有的钱都不足需求)
{
返回，不执行
}
if (当前值大于等于需求)
{
if (硬币加和等于需求)
{
flag = 1;
输出各面值
cout << endl;
}
return;
}
}
代码
#include<iostream>
#include<algorithm>
using namespace std;
int a[10000];// 硬币
int sum[10000];// 每种情况的加和，从后往前加
int ans[10000];// 记录当前的硬币组合
int N, M;
bool flag = 0;
// 动态规划 x 第几个开始取 num 硬币数量 jiahe 当前几个硬币加起来的钱
void dfs(int x, int num, int jiahe)
{
// 如果当前面值和加上剩下所有钱都不足 M则不继续递归
if (flag || jiahe + sum[x] < M)
{
return;
}
// 如果当前的面值和大于M则不继续递归
if (x == N || jiahe >= M)
{
if (jiahe == M)// 当前面值和等于M，就判断成功
{
flag = 1;
cout << ans[0];
for (int i = 1; i < num; i++)
{
cout << " " << ans[i];
}
cout << endl;
}
return;
}
ans[num] = a[x];// 取的硬币对应的面值
dfs(x + 1, num + 1, jiahe + a[x]);// 取当前硬币
dfs(x + 1, num, jiahe);// 不取当前硬币
}
int main()
{
cin >> N >> M;
for (int i = 0; i < N; i++)
{
cin >> a[i];
}
sort(a, a + N);// 对硬币面值进行排序
sum[N - 1] = a[N - 1];
for (int i = N - 2; i >= 0; i--)
{
sum[i] = sum[i + 1] + a[i];// 计算后缀和
}
// 从最初开始找
dfs(0, 0, 0);
if (!flag)
cout << "No Solution" << endl;
return 0;
}
