7 混合背包问题

短命女 2022-09-11 06:19 16阅读 0赞

**1. 问题描述：**

有 N 种物品和一个容量是 V 的背包。物品一共有三类：  
第一类物品只能用1次（01背包）；  
第二类物品可以用无限次（完全背包）；  
第三类物品最多只能用 si 次（多重背包）；  
每种体积是 vi，价值是 wi。  
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。

**输入格式**

第一行两个整数N，V，用空格隔开，分别表示物品种数和背包容积。接下来有 N 行，每行三个整数 vi，wi，si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。  
si = −1 表示第 i 种物品只能用1次；  
si = 0 表示第 i 种物品可以用无限次；  
si > 0 表示第 i 种物品可以使用 si 次；

**输出格式**

输出一个整数，表示最大价值。

**数据范围**

0 < N，V ≤ 1000  
0 < vi，wi ≤ 1000  
−1 ≤ si ≤ 1000

**输入样例**

4 5  
1 2 -1  
2 4 1  
3 4 0  
4 5 2

**输出样例：**

8  
来源：[https://www.acwing.com/problem/content/description/7/][https_www.acwing.com_problem_content_description_7]

**2. 思路分析：**

分析题目可以知道**混合背包问题**其实是将零一背包问题，完全背包问题和多重背包问题结合在了一起，其中的物品分别对应这三种背包问题，我们可以回忆一下这三种背包问题的状态表示，可以发现这三种背包问题的二维数组对应的状态表示都是一样的，其中dp\[i\]\[j\]为从前i个物品中选择且总体积不超过j的所有方案中能够获得的最大价值，对于第i个物品来说与前面的i - 1个物品属于哪一种情况是没有关系的，第i个物品只与当前属于哪一种背包问题有关系（状态表示都是一样的），根据属于哪一种背包问题使用对应的状态转移方程即可，所以我们只需要分类讨论即可，判断当前的物品属于哪一种背包问题那么就使用哪一种背包问题的状态转移方程；并且对于零一背包问题来说只有选或者不选两种选择，所以可以看成是多重背包问题的特殊情况，也即零一背包可以看成是多重背包中物品的上限个数为1的情况，那么我们可以将零一背包问题与多重背包问题归为一类进行讨论，由于这道题目的数据范围比较大所以需要使用[二进制优化][Link 1]来解决多重背包问题，并且对于这三种背包问题都是可以优化为一维数组的，所以最终我们可以使用一维数组来解决，dp\[V\]为背包容量为V的情况下能够获得的最大价值。零一背包问题和完全背包问题的一维状态转移方程为都是：dp\[j\] = max(dp\[j\], dp\[j - v\] + w)，只是在枚举体积的时候零一背包问题和多重背包问题需要逆序枚举，完全背包问题则是按顺序枚举。

**3. 代码如下：**

if __name__ == '__main__':
        # 因为三种背包问题的状态定义都是一样的只是在状态计算的时候状态转移方程不一样所以我们根据属于哪种情况分类讨论即可
        n, V = map(int, input().split())
        dp = [0] * (V + 1)
        for i in range(n):
            # v, w, s分别表示物品的体积, 价值和上限
            v, w, s = map(int, input().split())
            if s == 0:
                # s = 0的时候表示当前的物品可以选择无限个, 属于完全背包问题, 顺序枚举所有的体积
                for j in range(v, V + 1):
                    dp[j] = max(dp[j], dp[j - v] + w)
            else:
                # 零一背包问题属于特殊的多重背包问题所以当s = -1的时候物品上限的个数为1
                if s == -1:
                    s = 1
                # 多重背包问题经过二进制优化之后就变为了零一背包问题, 零一背包问题的一维数组解决需要逆序遍历
                k = 1
                while k <= s:
                    for j in range(V, k * v - 1, -1):
                        dp[j] = max(dp[j], dp[j - k * v] + k * w)
                    s -= k
                    k *= 2
                # 剩余的那个数字再做一下零一背包, 更新体积其实就是枚举当前这个数可以更新的所有体积
                if s > 0:
                    for j in range(V, s * v - 1, -1):
                        dp[j] = max(dp[j], dp[j - s * v] + s * w)
        print(dp[V])

[https_www.acwing.com_problem_content_description_7]: https://www.acwing.com/problem/content/description/7/
[Link 1]: https://blog.csdn.net/qq_39445165/article/details/120272536