【算法】动态规划专题⑦——多重背包问题+二进制分解优化python

目录 前置知识进入正题优化方法：二进制分解实战演练

---

前置知识

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

---

进入正题

多重背包问题I .acwing /problem/content/4/

题目描述

有 N N N 种物品和一个容量是 V V V 的背包。 第 i i i 种物品最多有 s i s_i si​ 件，每件体积是 v i v_i vi​，价值是 w i w_i wi​。

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

输入格式

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

输出格式

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

数据范围

0 < N , V ≤ 100 0 \lt N, V \le 100 0<N,V≤100 0 < v i , w i , s i ≤ 100 0 \lt v_i, w_i, s_i \le 100 0<vi​,wi​,si​≤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 + 47 = 1 + 2 + 413 = 1 + 2 + 4 + 6

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

---

实现步骤

对于每种物品，根据其数量mi进行二进制拆分，生成新的“物品”列表。初始化dp数组，dp[0]通常初始化为0，因为当容量为0时无法放入任何东西。遍历新生成的每个“物品”，然后从该物品的重量开始遍历到背包的容量C，更新dp数组。dp[j] = max(dp[j], dp[j-w[i]] + v[i]) 对于所有 j >= w[i] 最终，dp[C]将包含能够放入容量为C的背包中的最大价值。

注意

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

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

---

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

实战演练

多重背包问题II .acwing /problem/content/5/

题目描述

有 N N N 种物品和一个容量是 V V V 的背包。 第 i i i 种物品最多有 s i s_i si​ 件，每件体积是 v i v_i vi​，价值是 w i w_i wi​。

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

输入格式

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

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

输出格式

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

数据范围

0 < N ≤ 1000 0 \lt N \le 1000 0<N≤1000 0 < V ≤ 2000 0 \lt V \le 2000 0<V≤2000 0 < v i , w i , s i ≤ 2000 0 \lt v_i, w_i, s_i \le 2000 0<vi​,wi​,si​≤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 如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！ 如果喜欢的话，请给博主点个关注 谢谢