A logical error occured in knapsack memoization recurrsion problem and I can't figure out

Viewed 13

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)
0 Answers
Related