[PAT解题报告] Find More Coins
不难的题，给定n个硬币，问能否凑出m块钱。如果有解，输出字典序最小的解。
经典背包问题。现判断解的存在性，我们把钱币按面值由小到大排序，大于m的扔掉，排好后假设是a[0..n - 1]。
我们用bool数组can[x][y]表示用[x..n - 1]的硬币是否能凑出y块钱，
初值全是false，只有can[n][0] = true， 因为这表示什么硬币都不用，我们只能凑出0块钱。
递推：
can[i][j] = can[i + 1][j] || can[i + 1][j - a[i]];
这表示要用[i..n - 1]的硬币凑出j块钱，要么就是用[i + 1.. n - 1]已经凑好了，这样不需要第i个硬币。
要么用第i个硬币，并用[i + 1..n - 1]个硬币凑出j - a[i]块钱。
这样我们打出一个表来。
如何求字典序最小的解？
从第0个硬币开始考虑，对于第i个硬币，如果a[i + 1][m -
a[i]]为真，表示我们可以选择第i个硬币，并用剩余硬币凑出后面的钱，就选择第i个硬币，并且m -=
a[i]。这样我们就是从面值最小的考虑，在保证有解的前提下，尽可能选择面值较小的硬币，所以得到的解是字典顺序最小的。
代码：
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
bool can[10002][102];
int a[10002];
int main() {
int n,m;
scanf("%d%d",&n,&m);
for (int i = 0; i < n; ++i) {
scanf("%d",&a[i]);
if (a[i] > m) {
--i;
--n;
}
}
sort(a, a + n);
can[n][0] = true;
for (int i = n - 1; i >= 0; --i) {
for (int j = 0;j <= m; ++j) {
can[i][j] = can[i + 1][j] || ((j >= a[i]) && can[i + 1][j - a[i]]);
}
}
if (can[0][m]) {
bool have = false;
for (int i = 0; (i < n) && (m >= a[i]); ++i) {
if (can[i + 1][m - a[i]]) {
if (have) {
putchar(' ');
}
else {
have = true;
}
printf("%d",a[i]);
m -= a[i];
}
}
puts("");
}
else {
puts("No Solution");
}
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1068
投递腾讯音乐娱乐集团等公司8个岗位 >