9 分组背包问题

向右看齐 2022-08-28 15:52 196阅读 0赞

**1. 问题描述：**

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

**输入格式**

第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。接下来有 N 组数据：每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；每组数据接下来有 Si 行，每行有两个整数 vij，wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；

**输出格式**

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

**数据范围**

0 < N，V ≤ 100

0 < Si ≤ 100  
0 < vij，wij ≤ 100

**输入样例**

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

输出样例：

8  
来源：[https://www.acwing.com/problem/content/9/][https_www.acwing.com_problem_content_9]

**2. 思路分析：**

**分组背包问题**属于背包问题中经典问题，在分组背包问题中是将所有的物品进行分组，每一组的所有物品中至多选择一个；分组背包问题类似于多重背包问题，我们在状态定义的时候可以定义一个二维数组或者二维列表dp，其中dp\[i\]\[j\]表示从前i组物品中选，体积不超过j能够获得的最大价值，与多重背包是很像的，只是状态定义的时候意思是不同的；怎么样进行状态的计算呢？状态计算对应集合的划分，一般是找最后一个不同点，我们可以根据第i组中的物品选或者不选划分为s个子集，可以使用三层循环枚举，第一层循环枚举物品的组数，第二层循环枚举体积，第三层循环枚举当前这一组的所有物品表示选还是不选当前这一组的第k个物品，分组背包的二维状态转移方程为，由状态转移方程可知，我们使用到的都是上一层的状态而不是当前这一层的状态所以在枚举体积的时候需要逆序枚举这样我们就可以将二维数组优化为一维数组了：

dp\[i\]\[j\] = max(dp\[i - 1\]\[j\]，dp\[i - 1\]\[j - v\[i\]\[1\]\] + w\[i\]\[1\]，dp\[i - 1\]\[j - v\[i\]\[2\]\] + w\[i\]\[2\]，...dp\[i - 1\]\[j - v\[i\]\[s\]\] + w\[i\]\[s\])，s表示是当前这一组的第s个物品。

**3. 代码如下：**

if __name__ == '__main__':
        n, V = map(int, input().split())
        dp = [0] * (V + 1)
        for i in range(n):
            s = int(input())
            v, w = list(), list()
            for j in range(s):
                _v, _w = map(int, input().split())
                v.append(_v)
                w.append(_w)
            for j in range(V, -1, -1):
                for k in range(s):
                    if j >= v[k]: dp[j] = max(dp[j], dp[j - v[k]] + w[k])
        print(dp[V])

[https_www.acwing.com_problem_content_9]: https://www.acwing.com/problem/content/9/