运行时错误只能将列表（而不是“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

我怀疑函数定义的参数顺序与参数顺序之间存在不匹配，在参数顺序中，参数实际上被传递给多个调用之一

请注意，在回溯中：

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

第12行显示了不同的参数顺序knapSack(wt, val, W, n-1)

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

Answer 2

我认为这有一个简单的解决办法，如果你把循环放在第一个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]