2 / 5 Dynamic Programming: States & Transitions

The Key Forgot Capacity

items = [(2, 3), (3, 4)]      # (weight, value)
memo = {}

def best(i, cap):
    if i == len(items):
        return 0
    if i in memo:                     # cache keyed on i alone
        return memo[i]
    w, v = items[i]
    take = 0
    if w <= cap:
        take = v + best(i + 1, cap - w)
    res = max(take, best(i + 1, cap))
    memo[i] = res
    return res

print(best(0, 3))

What does this print, and what is the correct answer?

A

It prints 0. The correct answer is 7.

B

It prints 3. The correct answer is 4.

C

It prints 4, which is correct.

D

It prints 7. The correct answer is 4.