【算法】动态规划专题⑦ —— 多重背包问题 + 二进制分解优化 python 二进制优化：将多重背包问题转化为0-1背包

前置知识

【算法】动态规划专题⑤ —— 0-1背包问题 + 滚动数组优化 python
【算法】动态规划专题⑥ —— 完全背包问题 python

进入正题

多重背包问题I https://www.acwing.com/problem/content/4/

题目描述

有 $N$ 种物品和一个容量是 $V$ 的背包。
第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

输入格式

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

输出格式

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

数据范围

$0<N,V\le 100$
$0<v_i,w_i,s_i\le 100$

输入样例

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

输出样例：

10

在多重背包问题中，对于每种物品，你不仅可以选择是否放入背包，而且对于每种物品还有一个限制，即该物品最多可以放入的数量。
与0/1背包和完全背包不同：我们需要对每个物品的数量限制进行处理。

基本实现：

n, v = map(int, i
nput().split())
dp = [[0] * (v + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
 vi, wi, si = map(int, input().split())
 for j in range(1, v + 1):
 for k in range(min(si, j // vi) + 1):
 dp[i][j] = max(dp[i][j], dp[i - 1][j - k * vi] + k * wi)
print(dp[n][v])

时间复杂度为O(n*v*s)，有没有优化的方法呢？

优化方法：二进制分解

为了提高效率，我们可以采用二进制优化的方法来处理物品的数量限制。
具体来说，对于第i种物品，我们将其数量mi拆分为若干组，每一组的数量分别为(1, 2, 4, …, res)
这样做的目的是让这些组合能够通过不同的组合方式表示从1到mi的所有数字。

例如，假设某物品的数量限制为13，那么我们可以将其拆分为：

• 1 即(2^0)
• 2 即(2^1)
• 4 即(2^2)
• 6 (13 - (1+2+4) = 6)

这样，我们就可以用这四个新的“物品”组合出任何从1到13的数量。比如：

• 5 = 1 + 4
• 7 = 1 + 2 + 4
• 13 = 1 + 2 + 4 + 6

完成上述转换后，我们将问题转化为0-1背包问题，其中每组作为一个单独的“物品”。

实现步骤

1. 对于每种物品，根据其数量mi进行二进制拆分，生成新的“物品”列表。
2. 初始化dp数组，dp[0]通常初始化为0，因为当容量为0时无法放入任何东西。
3. 遍历新生成的每个“物品”，然后从该物品的重量开始遍历到背包的容量C，更新dp数组。

   dp[j] = max(dp[j], dp[j-w[i]] + v[i]) 对于所有 j >= w[i]

4. 最终，dp[C]将包含能够放入容量为C的背包中的最大价值。

注意

• 使用二进制优化可以显著减少计算量，特别是在物品的数量限制较大的情况下。
• 在实际实现时，需要注意边界情况的处理，如物品数量mi为0的情况。

通过这种方法，我们可以有效地解决多重背包问题，并找到在给定背包容量下可获得的最大价值。

好了，实际运用的时候到了

实战演练

多重背包问题II https://www.acwing.com/problem/content/5/

题目描述

有 $N$ 种物品和一个容量是 $V$ 的背包。
第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

输入格式

第一行两个整数，$N，V$，用空格隔开，分别表示物品种数和背包容积。

接下来有 $N$ 行，每行三个整数 $v_i,w_i,s_i$，用空格隔开，分别表示第 $i$ 种物品的体积、价值和数量。

输出格式

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

数据范围

$0<N\le 1000$
$0<V\le 2000$
$0<v_i,w_i,s_i\le 2000$

输入样例

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

输出样例：

10

本题数据范围增强了，考查多重背包的二进制优化方法。

code：

n, v = map(int, input().split())
v_w = [] # 存储物品的体积和价值的二进制分解
for i in range(1, n + 1):
 vi, wi, si = map(int, input().split())
 k = 1
 while si >= k:
 v_w.append((vi * k, wi * k)) # 二进制分解
 si -= k
 k *= 2
 # 处理剩余的部分
 if si > 0:
 v_w.append((vi * si, wi * si))
dp = [0] * (v + 1) # 滚动数组优化
for i, (vi, wi) in enumerate(v_w):
 for j in range(v, vi - 1, -1):
 dp[j] = max(dp[j], dp[j - vi] + wi)
print(dp[v])

时间复杂度优化为O(n*v*logs)

再进一步，利用单调队列维护窗口内最大值，避免重复计算
可以将时间复杂度优化为O(n*v)，
在此就不赘述了，属于进阶技巧，后续会更新

END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢