Basically, we need to pick the best according to the profits and capacity.
Here are the inputs and outputs
test0 = {
'input': {
'capacity': 165,
'weights': [23, 31, 29, 44, 53, 38, 63, 85, 89, 82],
'profits': [92, 57, 49, 68, 60, 43, 67, 84, 87, 72]
},
'output': 309
}
I tried to solve it using normal recursion and it worked fine RECURSION
def lc_rec(weights, profits, capacity, idx=0):
if idx == len(weights):
return 0
elif weights[idx] > capacity:
return lc_rec(weights, profits, capacity, idx+1)
else:
option1 = lc_rec(weights, profits, capacity, idx+1)
option2 = profits[idx] + lc_rec(weights, profits, capacity - weights[idx], idx+1)
return max(option1, option2)
I tried memoized recursion and some logical error occured and the outputs are not as expected MEMOIZED RECURSION
def lc_memo(weights, profits, capacity):
memo ={}
def mei(capacity, idx=0):
key = (capacity, idx)
if key in memo:
return memo[key]
elif weights[idx] > capacity:
memo[key] = 0
idx += 1
else:
option1 = mei(capacity, idx+1)
option2 = profits[idx] + mei(capacity - weights[idx], idx+1)
memo[key] = max(option1, option2)
return memo[key]
return mei(0,0)