4 多重背包问题 I（零一背包问题的扩展）

- 日理万妓 2022-09-11 00:04 176阅读 0赞

**1. 问题描述：**

有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。

**输入格式**

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。接下来有 N 行，每行三个整数 vi，wi，si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

**输出格式**

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

**数据范围**

0 < N，V ≤ 100  
0 < vi，wi，si ≤ 100

**输入样例**

4 5  
1 2 3  
2 4 1  
3 4 3  
4 5 2

**输出样例：**

10  
来源：[https://www.acwing.com/problem/content/description/4/][https_www.acwing.com_problem_content_description_4]

**2. 思路分析：**

**多重背包问题**其实是一维零一背包问题的扩展（物品在选择的次数上的限制不一样），零一背包问题是多重背包问题的特殊形式，零一背包问题每件物品只能够选0次或者是1次，所以总共有两种选择，对于多重背包问题，可以选择0，1，2...si个第i个物品（si为第i个物品的上限），所以总共有s + 1种选择，多重背包问题的状态转移方程为：dp\[j\] = max(dp\[j\]，dp\[j - vi\] + wi， dp\[j - 2vi\] + 2wi，...dp\[j - svi\] + swi)，可以发现多重背包问题的状态计算方程与一维的零一背包问题的状态计算方程式其实是很像的，是一维零一背包的扩展，所以我们可以在一维零一背包的基础上增加一个循环用来枚举选择第i个物品可以选的个数即可，其余的步骤都是一样的。因为这道题目的n，v，s都在100以内所以使用上面方法解决使可以通过的（时间复杂度为10 ^ 6），对于多重背包问题一般有三种写法，当数据规模不是特别大的时候可以使用当前朴素的多重背包写法，其余两种写法是对当前这种朴素版写法的优化，分别是二进制优化和单调队列优化写法，可以使用在数据规模比较大的情况。

**3. 代码如下：**

if __name__ == '__main__':
        n, V = map(int, input().split())
        dp = [0] * (V + 1)
        for i in range(n):
            # v表示第i件物品的体积, w表示第i件物品的价值, s表示第i件物品的上限
            v, w, s = map(int, input().split())
            for j in range(V, -1, -1):
                for k in range(s + 1):
                    if k * v <= j:
                        dp[j] = max(dp[j], dp[j - k * v] + k * w)
        print(dp[V])

[https_www.acwing.com_problem_content_description_4]: https://www.acwing.com/problem/content/description/4/