IndexError：背包问题超出列表索引范围

Question

问题问我要输入的权重，我可以保留的项目数和权重数组。它要求我计算可携带的最大重量（0-1背包：动态编程）

W：输入权重n：项目数wt：权重数组

当我执行此代码时，第10行出现索引错误。在我看来这是一个非常愚蠢的错误，在运行了几个小时的测试用例之后，我无法弄清楚。我用谷歌搜索发现的解决方案似乎在每个我写t [i] [j]

的地方都取值t [j] [i]

# Uses python3
import sys

def optimal_weight(W, wt, n):
     t = [[0 for x in range(n+1)] for y in range(W+1)]

     for i in range(1,n+1):
        for j in range(1,W+1):
             if wt[i-1]<=j :
                t[i][j]= max ( wt[i-1] + t[i-1][j-wt[i-1]] , t[i-1][j])
             else :
                t[i][j]= t[i-1][j]

     return t[n][W]

if __name__ == '__main__':
    arr = list(map(int, input().split()))
    W = arr[0]
    n = arr[1]
    wt= list(map(int, input().split()))
    print(optimal_weight(W, wt,n))

Answer 1

t = [[0 for x in range(n+1)] for y in range(W+1)]

您的外部列表维度为0..W，内部列表为0..n；即您的有效索引范围是t[0..W][0..n]。因此，您将需要[j][i]而不是[i][j]，因为您的i将转到n，而j将转到W。

或者，您可以翻转定义列表的方式：

t = [[0 for x in range(W+1)] for y in range(n+1)]