题目描述

blablabla

样例

blablabla

python3 代码

n, m = map(int, input().split())
v = [0]
w = [0]
for _ in range(n):
    vi, wi = map(int, input().split())
    v.append(vi)
    w.append(wi)

dp = [[0] * (m+1) for _ in range(n+2)]

for i in range(n, 0, -1):
    for j in range(m+1):
        dp[i][j] = dp[i+1][j]
        if j >= v[i]:
            dp[i][j] = max(dp[i][j], dp[i+1][j-v[i]]+w[i])

# print(dp)
value = m
res = ''
for i in range(1,n+1):
    if dp[i][value] == (dp[i+1][value-v[i]]+w[i]):
        print(i, end=' ')
        value -= v[i]