forked from Gitlink/forgeplus
20 lines
434 B
Python
20 lines
434 B
Python
# N件物品，一个容量为V的背包
|
||
N, V = map(int, input().split())
|
||
weight = []
|
||
val = []
|
||
|
||
for _ in range(N):
|
||
wi, vi = map(int, input().split())
|
||
weight.append(wi)
|
||
val.append(vi)
|
||
|
||
dp = [[0]*(V+1) for _ in range(N+1)]
|
||
|
||
for i in range(1, N+1):
|
||
for w in range(1, V+1):
|
||
dp[i][w] = dp[i-1][w]
|
||
if w-weight[i-1] >= 0:
|
||
dp[i][w] = max(dp[i][w], dp[i-1][w-weight[i-1]]+val[i-1])
|
||
|
||
print(dp[N][V])
|