多重背包问题 模板 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

    // 方法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 二进制优化
    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;
}