list index out of range for knapsack problem without repetition

Question

Problem introduction:

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).

Problem Description:

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 𝑊.

My code is as follows:

# 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))

My solution worked for the sample test cases given, but was rejected for one of the test cases:

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

May I know what could have resulted in the error or if there is a better way to implement a DP solution to this problem?

Answer 1

The only possible cause in my opinion is this statement:

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

There aren't any constraints which dictate that j-w[i-1] will be a valid index. Just replace it with

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