一、多重背包问题

背包问题为有N种物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i]，数量为Mi，得到的价值是value[i] ，没件物品只能使用一次，将这些物品装进背包，怎么装价值最高。

二、多重背包问题的解法

我们注意到01背包并没有要求物品不一样，因此我么可以把多重背包摊开，把Mi件第i中物品视作Mi种物品，没种只有一个，这就转换成一个01背包问题，具体的转化方式有两种

1、显示摊开

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;
	/-----将物品展开-----/
    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();
}

2、隐式展开

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背包内部加一个循环，将同一件物品的k件进行展开----/
            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();
}

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]);
            }

这段展开代码的含义：对于物品i，在背包容量足够的情况下，我可以选择放0-nums[i]件，dp[j]要记录价值最大的一种放置方法时的最大价值。由于背包容量j是从后向前遍历的，因此dp[j - k * weight[i]]是还没有经历过第i轮计算的，其内不可能还有i物品，因此dp[j - k * weight[i]] + k * value[i]就是背包内放了k件i物品时的最大价值。