9. 分组背包问题
摘要
Title: 9. 分组背包问题
Tag: 分组背包
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
9. 分组背包问题
-
题意
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。 -
思路
分组背包：第i组物品最多选1个
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25'''
Author: NEFU AB-IN
Date: 2022-03-06 15:42:55
FilePath: \ACM\Acwing\9.py
LastEditTime: 2022-03-06 15:42:56
'''
N = 110
v, w = [[0] * N for _ in range(N)], [[0] * N for _ in range(N)]
s, dp = [0] * N, [0] * N
n, m = map(int, input().split())
for i in range(1, n + 1):
s[i] = int(input())
for j in range(1, s[i] + 1):
v[i][j], w[i][j] = map(int, input().split())
for i in range(1, n + 1):
for j in range(m, -1, -1):
for k in range(1, s[i] + 1):
if j - v[i][k] >= 0:
dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k])
print(dp[m])
