多重背包问题 模板 C++实现
问题：有 n 种物品和一个容量是 c 的背包。
第 i 种物品最多有 num [ i - 1 ] 件，每件体积是 weight [ i - 1] ，价值是 value [ i - 1 ] 。
求解将哪些物品装入背包，可使物品重量总和不超过背包容量，且价值总和最大。输出最大价值。
算法1：三重循环
内层循环用于考虑当前物品 i 可以被选择的数量，k 代表选择当前物品的数量。
与完全背包相比，多重背包问题只多了 不可超过最大可选第 i 件物品数量 nums [ i - 1 ] 这一个限制，加上即可。
循环的条件 k <= num [ i - 1 ] && k * weight [ i ] <= j 确保了两个限制：不超过物品的最大可选数量 num [ i - 1 ] ，以及所选物品的总体积 k * weight [i - 1] 不超过当前背包容量 j 。
此方法的 时间复杂度为：O(n³) 。
代码：
// 方法1
int dp[4+1][20+1];
memset(dp, 0, sizeof(dp));// 初始化dp（方法1）
for (int i = 1; i <= n; ++i)for (int j = 0; j <= c; ++j)for (int k = 0; k <= num[i - 1] && k * weight[i - 1] <= j; k++)dp[i][j] = max(dp[i][j], dp[i - 1][j - weight[i - 1] * k] + value[i - 1] * k);
cout << dp[n][c] << endl;算法2：
为了降低时间复杂度，我们要把 多重背包问题 转换成 0/1背包问题 。
如上图所示，这样简单拆分，只是把 O(n³) 的时间复杂度变成了 O(n²) ，但 n 变多了，总体运行次数没有变化。那么我们是否存在一种方式，我们不需要枚举 n 次 i 物品，就能够表示 n 个 i 物品呢？
我们的十进制数可以用二进制数来表示。二进制 0 1 2 4 ... ，可以表达从 0 到 7 的数字，同样的，假设一共有 7 件 a 物品，我们可以把他分为 1，2，4 的组合，把他分为 3 件物品，这样的话如果我们想装入 3 件 a 物品，只需要把 1 件和 2 件装入即可。除此之外，要创建新的 weight1 、value1 数组，用来存储重新分组的值。
那么我们发现，此时我们利用 O(logn) 级别的数字表示了 O(n) 。时间上做了非常大的优化。而这种优化方式被称作 二进制优化 。
代码：
int dp[20 + 1] = { 0 }, cnt = 0, weight1[20] = { 0 }, value1[20] = { 0 };
for (int i = 0; i < n; i++){int k = 1, w = weight[i], v = value[i], m = num[i];// 进行 “打包” 转换：二进制优化，转换成01背包while (k < m){weight1[cnt] = k * w, value1[cnt++] = k * v;m -= k;k *= 2;}if (m > 0) weight1[cnt] = m * w, value1[cnt++] = m * v;// 剩余的分一组
}// 利用01背包中的空间优化模板求解。for (int i = 0; i < cnt; i++)for (int j = c; j >= weight1[i]; j--)dp[j] = max(dp[j], dp[j - weight1[i]] + value1[i]);
cout << dp[c] << endl;完整代码：
#include<iostream>using namespace std;int main() {// weight重量 value价值 num每件物品的个数int weight[4] = { 3,5,2,8 }, value[4] = { 4,6,1,9 }, num[4] = { 3, 4, 6, 1 }; int n = 4, c = 20;// 物品个数n，背包容量c// 方法1int dp[4+1][20+1];memset(dp, 0, sizeof(dp));// 初始化dp（方法1）for (int i = 1; i <= n; ++i)for (int j = 0; j <= c; ++j)for (int k = 0; k <= num[i - 1] && k * weight[i - 1] <= j; k++)dp[i][j] = max(dp[i][j], dp[i - 1][j - weight[i - 1] * k] + value[i - 1] * k);cout << dp[n][c] << endl;/*// 方法2 二进制优化int dp[20 + 1] = { 0 }, cnt = 0, weight1[20] = { 0 }, value1[20] = { 0 };for (int i = 0; i < n; i++){int k = 1, w = weight[i], v = value[i], m = num[i];// 进行 “打包” 转换：二进制优化，转换成01背包while (k < m){weight1[cnt] = k * w, value1[cnt++] = k * v;m -= k;k *= 2;}if (m > 0) weight1[cnt] = m * w, value1[cnt++] = m * v;// 剩余的分一组}// 利用01背包中的空间优化模板求解。for (int i = 0; i < cnt; i++)for (int j = c; j >= weight1[i]; j--)dp[j] = max(dp[j], dp[j - weight1[i]] + value1[i]);cout << dp[c] << endl;
*/return 0;
}