1

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?

husseljo
  • 33
  • 4
  • Does this answer your question? [Printing Items that are in sack in knapsack](https://stackoverflow.com/questions/23186171/printing-items-that-are-in-sack-in-knapsack) – ggorlen Feb 01 '21 at 20:49

0 Answers0