列表索引超出背包问题的范围而不重复

Question

问题介绍：

You are given a set of bars of gold and your goal is to take as much gold as possible into your bag. There is just one copy of each bar and for each bar you can either take it or not (hence you cannot take a fraction of a bar).

问题描述：

Task. Given gold bars, find the maximum weight of gold that fits into a bag of capacity .

Input Format. The first line of the input contains the capacity of a knapsack and the number of bars of gold. The next line contains integers 0, 1, . . . , −1 defining the weights of the bars of gold.

Constraints. 1 ≤ ≤ 10⁴ ; 1 ≤ ≤ 300; 0 ≤ 0, . . . , −1 ≤ 10⁵.

Output Format. Output the maximum weight of gold that fits into a knapsack of capacity .

我的代码如下：


# Uses python3
import sys

def optimal_weight(W, w):
    # write your code here
    n = len(w)
    value = [[0] * (W+1) for i in range(n+1)]
    
    for i in range(1, n+1):
        for j in range(1, W+1):
            value[i][j] = value[i-1][j]
            # does not check every single possible weight
            # must loop through all diagonally top left cells
            v = w[i-1] + value[i-1][j-w[i-1]]
            
            if v <= j:
                value[i][j] = max(v, value[i][j])
            
    return value[n][W]

if __name__ == '__main__':
    input = sys.stdin.read()
    W, n, *w = list(map(int, input.split()))
    print(optimal_weight(W, w))

我的解决方案适用于给定的样本测试用例，但被拒绝了其中一个测试用例：

Failed case #7/14: Wrong answer
wrong output format: list index out of range
(Time used: 0.01/10.00, memory used: 11313152/2147483648.)

我可以知道是什么导致了这个错误，或者是否有更好的方法来实现这个问题的 DP 解决方案？

Answer 1

在我看来，唯一可能的原因是这句话：

v = w[i-1] + value[i-1][j-w[i-1]]

没有任何限制规定 j-w[i-1] 将是一个有效的索引。只需将其替换为

if j-w[i-1] >= 0:
    v = w[i-1] + value[i-1][j-w[i-1]]

列表索引超出背包问题的范围而不重复

list index out of range for knapsack problem without repetition

python

arrays

algorithm

knapsack-problem

dynamic-programming