多重背包.
你会发现这既不是01背包,也不是完全背包.前者每个物品只有一个,后者每个物品都有无限多个,这里每个物品(砝码)都有有限个,并且是到达型问题.
思路是枚举每个砝码的个数,然后转化成01背包,我不知道这样说是不是很准确,先看代码:
dp[0] = true; // 注意初始化
for (int i = 0; i < 6; i++)
for (int k = 1; k <= ct[i]; k++)
for (int j = 1000; j >= s[i]; j--) // 总重<=1000
dp[j] |= dp[j - s[i]];
其中,dp[j]表示能否得到重量j.
很显然,枚举砝码个数并不是说用一个变量k记录当前个数,然后dp[j] |= dp[j - k * s[i]]. ①
正确的做法是执行ct[i]遍的第三层循环. ②
现在,结合01背包的数组覆盖性质再想一想.
①相当于把每个物品分解为ct[i]个数量只有一个的物品,他们的重量为s[i], 2 * s[i], 3 * s[i], ... , ct[i] * s[i].
②相当于把每个物品分解为c[i]个数量只有一个的物品,他们的重量均为s[i].
到此结束.
#include <algorithm> #include <cstdio> #include <cstring> #include <iostream> using namespace std; int s[6] = {1, 2, 3, 5, 10, 20}, ct[6]; bool dp[1010]; int main() { for (int i = 0; i < 6; i++) cin >> ct[i]; dp[0] = true; for (int i = 0; i < 6; i++) for (int k = 1; k <= ct[i]; k++) for (int j = 1000; j >= s[i]; j--) dp[j] |= dp[j - s[i]]; int ans = 0; for (int i = 1; i <= 1000; i++) if (dp[i]) ans++; cout << "Total=" << ans << endl; return 0; }View Code