运行时错误 - 只能将列表（而不是 "int"）连接到列表

Question

我一直在使用递归+记忆做 0-1 背包问题。

我的代码：

def knapSack(W, wt, val, n):
    '''
    :param W: capacity of knapsack 
    :param wt: list containing weights
    :param val: list containing corresponding values
    :param n: size of lists
    :return: Integer
    '''
    t = [[-1 for x in range(W + 1)] for j in range(n + 1)]
    if n == 0 or W == 0: 
        return 0
    if t[n][W] != -1: 
        return t[n][W] 
    elif wt[n-1] <= W: 
        t[n][W] = max(val[n-1]+knapSack(W-wt[n-1],wt,val,n-1),knapSack(W,wt,val,n-1))
        return t[n][W] 
    elif wt[n-1] > W: 
        t[n][W] = knapSack(wt, val, W, n-1) 
        return t[n][W]

为什么我会收到运行时错误。

Runtime ErrorTraceback (most recent call last):
  File "/home/e8c2fc67721232cbee976a6adfc2c990.py", line 41, in <module>
    print(knapSack(W,wt,val,n))
  File "/home/e8c2fc67721232cbee976a6adfc2c990.py", line 12, in knapSack
    t[n][W] = knapSack(wt, val, W, n-1) 
  File "/home/e8c2fc67721232cbee976a6adfc2c990.py", line 5, in knapSack
    t = [[-1 for x in range(W + 1)] for j in range(n + 1)]
  File "/home/e8c2fc67721232cbee976a6adfc2c990.py", line 5, in <listcomp>
    t = [[-1 for x in range(W + 1)] for j in range(n + 1)]
TypeError: can only concatenate list (not "int") to list

这是我遇到的运行时错误详情。

Answer 1

我认为有一个简单的解决方法，只要将循环放在第一个 if 下方即可。

if n == 0 or W == 0: 
        return 0
t = [[-1 for x in range(W + 1)] for j in range(n + 1)]
if t[n][W] != -1: 
        return t[n][W] 
elif wt[n-1] <= W: 
    t[n][W] = max(val[n-1]+knapSack(W-wt[n-1],wt,val,n-1),knapSack(W,wt,val,n-1))
        return t[n][W] 
elif wt[n-1] > W: 
    t[n][W] = knapSack(wt, val, W, n-1) 
    return t[n][W]

Answer 2

我怀疑你函数定义的 parameter-order 和 argument-order[=26= 不匹配] 其中 args 实际上被传递给许多调用之一。

请注意，在回溯中：

在第 41 行，它将 arg-order 显示为 print(knapSack(W,wt,val,n))

在第 12 行显示不同的 arg-order knapSack(wt, val, W, n-1)

对于条件 elif wt[n-1] > W:，您对 knapSack() 的递归调用肯定是以错误的顺序传递参数。

运行时错误 - 只能将列表（而不是 "int"）连接到列表

Runtime Error - can only concatenate list (not "int") to list

python

recursion

knapsack-problem

memoization