5 多重背包问题 II（二进制优化-转为零一背包问题求解）

一时失言乱红尘 2022-09-11 06:16 120阅读 0赞

**1. 问题描述：**

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

**输入格式**

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

**输出格式**

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

**数据范围**

0 < N ≤ 1000  
0 < V ≤ 2000  
0 < vi，wi，si ≤ 2000

**输入样例**

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

**输出样例：**

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

**2. 思路分析：**

这道题目其实与第[4][]题多重背包I是一样的，只是在数据范围上有所区别，这道题目的N，V，S最大都超过1000所以如果使用多重背包I中的暴力求解的方法那么时间复杂度为10 \*\* 9，所以一定会超时，我们需要使用更加优秀的做法才可以解决这道题目；这里可以使用**二进制优化**的方法然后就可以将多重背包问题转化为零一背包问题，我们知道要想表示0 ~ 11...1(n位二进制数字)的数字，需要n个对应位置为1的二进制数字，例如7(10) = 111(2)，可以使用三位二进制数字分别为001，010，100他们组合就可以表示0~111(2)中的所有数字；二进制优化就是基于这个思想，但是因为每个物品的上限s可能不是2的整数次幂，这里我们采用的一种方法是让s一直减去2的整数次幂直到不能够减为止，例如物品的上限个数为10，那么减去1，2，4之后得到的是3，我们需要把1，2，4，3对应的体积和价值存储到v和w中；对于每一个物品都是这样操作，最终就可以将多重背包问题转为零一背包问题，对于v，w中的物品我们可以选或者不选，这样就可以枚举所有二进制表示中的组合方案了，在枚举的过程中一定是可以枚举出答案的。

**3. 代码如下：**

if __name__ == '__main__':
        # 因为数据规模比较大所以需要使用二进制进行优化
        n, V = map(int, input().split())
        v, w = list(), list()
        for i in range(n):
            # 当前这个物品的体积, 价值和物品能够选择的上限
            _v, _w, s = map(int, input().split())
            k = 1
            while k <= s:
                v.append(k * _v)
                w.append(k * _w)
                s -= k
                k *= 2
            # s不是2的整数次幂所以需要添加上枚举剩余的物品的体积来更新所有背包容量下的最大价值
            if s > 0:
                v.append(s * _v)
                w.append(s * _w)
        dp = [0] * (V + 1)
        # 最终转化为零一背包问题, 其实零一背包问题在优化的时候枚举所有可能的组合方案这样一定可以求出最佳的那个方案
        n = len(v)
        for i in range(n):
            for j in range(V, v[i] - 1, -1):
                dp[j] = max(dp[j], dp[j - v[i]] + w[i])
        print(dp[V])

if __name__ == "__main__":
         n, V = map(int, input().split())
         dp = [0] * (V + 1)
         for i in range(n):
              v, w, s = map(int, input().split())
              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_5]: https://www.acwing.com/problem/content/description/5/
[4]: https://blog.csdn.net/qq_39445165/article/details/120211348