281. 硬币

2024-05-11 00:58

文章标签 硬币 281

本文主要是介绍281. 硬币，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：硬币

*算法分析：
初看起来就是个简单的多重背包， $C_i$ 不大于1000，二进制拆分最多拆出10个数，这样时间复杂度在 $10^8$ ，勉强。提交后，数据强，超时。以下是标准二进制拆分超时代码。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n, m, A[110], a[1010], f[100010];
int main()  // 二进制拆分，超时  
{while (1){scanf("%d%d", &n, &m);if (!n && !m) break;for (int i = 1; i <= n; ++i) scanf("%d", &A[i]);int s = 0;for (int i = 1; i <= n; ++i){int c; scanf("%d", &c);int t = 1;while (c >= t){a[++s] = t * A[i];c -= t; t *= 2;}if (c > 0) a[++s] = c * A[i];}memset(f, 0, sizeof(f));f[0] = 1;for (int i = 1; i <= s; ++i)for (int j = m; j >= a[i]; --j)f[j] = f[j] || f[j-a[i]];int ans = 0;for (int j = 1; j <= m; ++j) ans += f[j];printf("%d\n", ans);}return 0;
}

据说用单调队列优化多重背包，可以达到 $O (n * m)$ 。以后有时间再补充。下面算法参考进阶指南。想法很巧妙。

用 $u s e d [j]$ 表示在 $f [j]$ 阶段为i时，体积为j，此时为true的情况下至少需要多少枚第i种硬币。采用一种贪心策略：让 $u s e d [j]$ 转移时，尽量不选第i种硬币。

也就是，当 $f [j - a [i]]$ 为true时，如果此时 $f [j]$ 已经为true，则不执行dp转移。否则才让 $f [j] = f [j] - a [i]$ ，并且 $u s e d [j] = u s e d [j - a [i]] + 1$ 。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n, m, A[110], C[110], f[100010], used[100010];
int main()  
{while (1){scanf("%d%d", &n, &m);if (!n && !m) break;for (int i = 1; i <= n; ++i) scanf("%d", &A[i]);for (int i = 1; i <= n; ++i) scanf("%d", &C[i]);memset(f, 0, sizeof(f));f[0] = 1;for (int i = 1; i <= n; ++i){for (int j = 0; j <= m; ++j) used[j] = 0;for (int j = A[i]; j <= m; ++j)if (!f[j] && f[j-A[i]] && used[j-A[i]] < C[i]){f[j] = 1;used[j] = used[j-A[i]] + 1;}}int ans = 0;for (int j = 1; j <= m; ++j) ans += f[j];printf("%d\n", ans);}return 0;
}