Hello I'm trying to solve this dp problem: https://vjudge.net/problem/UVA-990
I'm able to solve the initial problem result using this code below:
I used recursion and a memo table arr to optimize the code.
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)
However I have no idea how to keep track of the chosen items. I was thinking to store all indices of chosen treasures of the maxGold() output and print them later in a loop for instance.
One approach I had was to add a paramter to the maxGold() function and append to it the indices and return two result and the indices list from the function like the following:
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
However I ran into many tuple/integer type, subscriptable,iteratable errors. from this specific line even after trying to get a round the tuple output due to several outputs :
answer=max(maxGold(n-1,T,l)[0],gold[n]+maxGold(n-1,T-time[n],l2)[0])
And honestly I'm uncertain whether this approach is the right one.
Any hints?