【算法】动态规划专题⑧ —— 分组背包问题 python

前置知识

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

进入正题

分组背包问题的详细解析

1. 问题定义

在 分组背包问题 中，物品被划分为若干组，每组内的物品互斥（只能选择其中一个或不选）。
给定背包容量 (C)，每组物品的价值和重量不同，目标是在不超过背包容量的前提下，最大化总价值。

2. 动态规划状态定义

状态定义：
设 dp[i][j] 表示前 (i) 组物品，背包容量为 (j) 时的最大总价值。
状态转移方程：
对于第 (i) 组中的每个物品 (k)，在容量允许的情况下，选择是否将其加入背包：

其中 $w_k$ 和 $v_k$ 是物品 (k) 的重量和价值。

3. 一维数组空间优化

优化思路：
将二维数组压缩为一维数组 dp[j]，表示容量为 (j) 时的最大价值。
为确保每组内物品 只选一个，需 倒序遍历容量（类似01背包）。
转移方程优化：

4. 算法实现步骤

输入处理：
读取物品分组信息、背包容量。
初始化：
一维数组 dp 初始化为全0。
遍历每组物品：
对每组内的所有物品，逆序更新容量对应的最大价值。
输出结果：
dp[capacity] 即为最大总价值。

5. 关键点解析

遍历顺序：
- 外层循环遍历组，保证每组只处理一次。
- 内层循环逆序遍历容量，确保每组内的物品不会被重复选取。
时间复杂度：
O(G*C*K)，其中 (G) 为组数，(C) 为容量，(K) 为每组最多物品数。
空间复杂度：
O(C)，优化后仅需一维数组。

6. 示例分析

输入：

第1组物品：[(2,3), (3,4)]
第2组物品：[(4,5), (1,2)]
背包容量：(5)

执行过程：

处理第1组：
- 容量5：可选取物品2（重量3，价值4），更新 dp[5] = max(0, dp[5-3]+4) = 4。
- 容量3：选取物品1（重量2，价值3），dp[3] = 3。
处理第2组：
- 容量5：可选取物品4（重量1，价值2），更新 dp[5] = max(4, dp[5-1]+2) = max(4, dp[4]+2)。
  其中 dp[4] 在第1组处理后为4（选物品2，重量3，价值4），因此 dp[5] = 4+2 = 6。
- 容量4：选取物品3（重量4，价值5），更新 dp[4] = 5。

最终结果：
最大价值为 (6)（选第1组的物品2和第2组的物品4）。

实战演练

分组背包问题 https://www.acwing.com/problem/content/9/

题目描述

有 $N$ 组物品和一个容量是 $V$ 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 $v_{ij}$ ，价值是 $w_{ij}$ ，其中 $i$ 是组号， $j$ 是组内编号。
求解
将哪些物品装入背包，使物品总体积不超过背包容量且总价值最大。

输入格式

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

接下来有 $N$ 组数据：

每组数据第一行有一个整数 $S_i$ ，表示第 $i$ 个物品组的物品数量；
每组数据接下来有 $S_i$ 行，每行有两个整数 $v_{ij}, w_{ij}$ ，用空格隔开，分别表示第 $i$ 个物品组的第 $j$ 个物品的体积和价值；

输出格式

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

数据范围

$\lt N, V \le 100$
$\lt S_i \le 100$
$\lt v_{ij}, w_{ij} \le 100$

输入样例

输出样例：

题解code：

python">n, v = map(int, input().split())
dp = [[0] * (v + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    si = int(input())
    for _ in range(si):
        vij, wij = map(int, input().split())
        for j in range(0, v + 1):
            if j < vij:
                dp[i][j] = max(dp[i][j], dp[i - 1][j])
            else:
                dp[i][j] = max(dp[i][j], dp[i - 1][j], dp[i - 1][j - vij] + wij)
print(dp[n][v])

优化：

python"># 读入数据
n, v = map(int, input().split())
groups = []
for _ in range(n):
    si = int(input())
    group = [list(map(int, input().split())) for _ in range(si)]
    groups.append(group)

dp = [0] * (v + 1)

for i in range(1, n + 1):
	# 倒序枚举
    for j in range(v, -1, -1):
        for vi, wi in groups[i - 1]:
            if j >= vi:
                dp[j] = max(dp[j], dp[j - vi] + wi)
print(dp[v])