题目大意:给出五种硬币的价值和数量,问如何用最多的硬币组成另一个数
解题思路:完全背包问题加纪录路径
#include <cstdio>
#include <cstring>
const int N = 10010;
int val[4] = {1, 5, 10, 25};
int dp[N], path[N], use[N], num[4], ans[30];
int n;
void solve() {
memset(dp, -1, sizeof(dp));
memset(path, -1, sizeof(path));
dp[0] = 0;
path[0] = 0;
for (int i = 0; i < 4; i++) {
memset(use, 0, sizeof(use));
for (int j = val[i]; j <= n; j++) {
if (dp[j] < dp[j - val[i]] + 1 && dp[j - val[i]] != -1 && use[j - val[i]] < num[i]) {
dp[j] = dp[j - val[i]] + 1;
use[j] = use[j - val[i]] + 1;
path[j] = j - val[i];
}
}
}
if (dp[n] == -1) {
printf("Charlie cannot buy coffee.\n");
return ;
}
memset(ans, 0, sizeof(ans));
int t = n;
while (t != 0) {
ans[t - path[t]]++;
t = path[t];
}
printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n", ans[1], ans[5], ans[10], ans[25]);
}
int main() {
while (scanf("%d", &n)) {
int Sum = n;
for (int i = 0; i < 4; i++) {
scanf("%d", &num[i]);
Sum += num[i];
}
if (!Sum) break;
solve();
}
return 0;
}