多重背包理论基础

多重背包概念：
每件物品有价值、重量、数量，从中选取物品放入背包中使得价值最大

多重背包和01背包是非常像的：
对于多重背包每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。

这种方式来实现多重背包的代码如下：

void test_multi_pack() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    vector<int> nums = {2, 3, 2};
    int bagWeight = 10;
    //通过将重复的物品放入数组中，来实现将多重背包转换成01背包
    for (int i = 0; i < nums.size(); i++) {
        while (nums[i] > 1) { // nums[i]保留到1，把其他物品都展开
            weight.push_back(weight[i]);
            value.push_back(value[i]);
            nums[i]--;
        }
    }
	//01背包问题求解
    vector<int> dp(bagWeight + 1, 0);
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
        for (int j = 0; j <= bagWeight; j++) {
            cout << dp[j] << " ";
        }
        cout << endl;
    }
    cout << dp[bagWeight] << endl;

}
int main() {
    test_multi_pack();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

另一种实现方式即把每种商品遍历的个数放在01背包里面再遍历一遍：遍历出使用0~n个当前物品的情况

解析：
在双层for内添加一个for来选择你添加的物品个数。

dp【j】的实现：
dp【j】最终值的得到是依次遍历出所有情况（双层for来实现），然后选择更大的值，最后dp【j】代表的就是最大值。

使用第三个for的解释：
因此我们使用双层for遍历出所有情况即可。假设当前物品有n个，那么当前物品的所有情况就是，不选择当前物品，选择1个当前物品，选择2个当前物品…选择n个当前物品。第三个for就是选择0~n个当前物品，虽然k从1开始，但是原先的dp【j】就代表0，所以是选择0 ~n个当前物品的情况

此代码即

• 将1个当前物品放入背包中实现的最大价值，和不将1个当前物品放入背包中实现的最大价值。这两种方式取max。
• 将2个当前物品放入背包中实现的最大价值，和不将2个当前物品放入背包中实现的最大价值。这两种方式取max。
• …
• 将n个当前物品放入背包中实现的最大价值，和不将n个当前物品放入背包中实现的最大价值。这两种方式取max。

void test_multi_pack() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    vector<int> nums = {2, 3, 2};
    int bagWeight = 10;
    vector<int> dp(bagWeight + 1, 0);


    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            // 以上为01背包，然后加一个遍历个数
            for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) { // 遍历个数
                dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);
            }
        }
        // 打印一下dp数组
        for (int j = 0; j <= bagWeight; j++) {
            cout << dp[j] << " ";
        }
        cout << endl;
    }
    cout << dp[bagWeight] << endl;
}
int main() {
    test_multi_pack();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26