python-3.x - 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))

标签： python-3.xlistdynamic-programmingknapsack-problemindex-error

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