0-1背包

0-1背包微调一下, 最大的改变是, 原先dp[j]表示体积恰好等于j时的最大价值.
现在修改为体积恰好为j时的最大价值与具体方案, (返回值是一个长度为2的tuple)

时间复杂度

O(N * V)

Python 代码

N, V = map(int, input().split())
dp = [[float("-inf"), []] for _ in range(V + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    v, w = map(int, input().split())
    for j in range(V, v - 1, -1):
        a = dp[j][0]
        b = dp[j - v][0] + w
        if a < b:
            dp[j][0] = dp[j - v][0] + w
            dp[j][1] = dp[j - v][1] + [i]
        elif a == b and dp[j][1] > dp[j - v][1] + [i]:
            dp[j][1] = dp[j - v][1] + [i]

ans = float("-inf")
res = []
for j in range(V + 1):
    if dp[j][0] > ans:
        ans = dp[j][0]
        res = dp[j][1]
    elif dp[j][0] == ans and dp[j][1] < res:
        res = dp[j][1]
print(" ".join(map(str, res)))