I am solving this problem Dividing Coins from uva. The problem is a variation of the well known 0/1 knapsack problem. I am trying to tweak my 0/1 knapsack implementation a bit to solve this problem. I have tested my code with many test cases offline and it works fine, but when I submit my code I get a Runtime Error.
When I comment out the lines where I check if the result of a subproblem is found in the dictionary. I get Time Limit Exceeded Error.
I can’t tell exactly where the problem is. However, I feel that I am not memoizing the right thing.
May you please have a look at my code and try to help? Thank you!
def recSolve(vals, remW, allItm, idx, mem):
if idx >= allItm or remW <= 0: # remW is the remaining amount the user could get (not exceeding total/2)
return 0
# check if it is in mem already
if (remW, idx) in mem:
return mem[(remW, idx)]
# wight of the current item is more than the remaninig weight, skip to the next item
if vals[idx] > remW:
return recSolve(vals, remW, len(vals), idx+1, mem)
else:
# choose either picking the item or not (maximize the val)
pickIt = recSolve(vals, remW - vals[idx], len(vals), idx+1, mem) + vals[idx]
dontPickIt = recSolve(vals, remW, len(vals), idx+1, mem)
res = max(pickIt, dontPickIt)
mem[(remW, idx)] = res
return res
def solve(vals, remW):
mem = {}
return recSolve(vals, remW, len(vals), 0, mem)
def takeInput():
for i in range(int(input())):
leng = input() # not used
coins = input()
vals = [int(i) for i in coins.split(' ')] # the coins
tot_w = sum(vals)
res= solve(vals, tot_w//2) # maximizing the summation while not exceeding totalCoins/2
print(tot_w - res - res) # getting the difference
takeInput()