python - 跟踪动态规划中的项目（类似于背包问题）

Question

您好我正在尝试解决这个 dp 问题：https ://vjudge.net/problem/UVA-990

我可以使用下面的代码解决最初的问题结果：

我使用递归和备忘录表 arr 来优化代码。

s=list(map(int,input().split()))
t=s[0] #seconds allowed under water
w=s[1] #w 
n=int(input()) #number of treasures
depth=[-1] 
gold=[-1]
time=[-1]
for i in range(3):
    q=list(map(int,input().split()))
    depth.append(q[0])
    gold.append(q[1])
    time.append(q[0]*w*3)

arr = [[-1]*(t+1) for i in range(0,(n+1))]

def maxGold(n,T):
    if n==0 or T==0:
        return 0
    if arr[n][T]!=-1:
        return arr[n][T]
    if time[n]>T:
        answer=maxGold(n-1,T)
    else:
        answer=max(maxGold(n-1,T),gold[n]+maxGold(n-1,T-time[n]))
    arr[n][T]=answer
    return answer

result=maxGold(n,t)
print(result)

但是我不知道如何跟踪所选项目。我正在考虑存储 maxGold() 输出的所选宝藏的所有索引，并稍后在循环中打印它们。

我的一种方法是向 maxGold() 函数添加一个参数，并将索引附加到它，然后从函数返回两个结果和索引列表，如下所示：

def maxGold(n,T,l):
    if n==0 or T==0:
        return 0,l
    if arr[n][T]!=-1:
        return arr[n][T],l
    if time[n]>T:
        answer=maxGold(n-1,T,l)
    else:
        l2=l[:]
        l2.append(n)
        answer=max(maxGold(n-1,T,l)[0],gold[n]+maxGold(n-1,T-time[n],l2)[0])
    arr[n][T]=answer
    return answer,l

result=maxGold(n,t,[])
print(result[0])
list_of_indices=result[1]
length=len(list_of_indices)

#proceed outputs

但是我遇到了许多元组/整数类型、可下标、可迭代的错误。即使由于多个输出而尝试对元组输出进行一轮循环后，也可以从该特定行开始：

answer=max(maxGold(n-1,T,l)[0],gold[n]+maxGold(n-1,T-time[n],l2)[0])

老实说，我不确定这种方法是否正确。

有什么提示吗？

标签： pythonrecursiondynamic-programmingknapsack-problem