Knapsack - Unbounded - DP - v1

"""
"""
def unbounded_knapsack(capacity, weights, values, index, memo):
    # base case:
    if index == 0:
        return (capacity // weights[0]) * values[0]

    # Return previously calculated value if available.
    if memo[index][capacity] != -1:
        return memo[index][capacity]

    # Case 1: Do not take the current item.
    exclude = unbounded_knapsack(capacity, weights, values, index - 1, memo)

    # Case 2: Take the current item if its weight is less than or equal to capacity.
    include = float('-inf')
    if weights[index] <= capacity:
        include = values[index] + unbounded_knapsack(capacity - weights[index], weights, values, index, memo)

    # Store the result in the memoization table.
    memo[index][capacity] = max(include, exclude)
    return memo[index][capacity]

capacity = 100
values = [10, 30, 20]
weights = [5, 10, 15]
num_items = len(values)
memo = [[-1 for _ in range(capacity + 1)] for _ in range(num_items)]
print(unbounded_knapsack(capacity, weights, values, num_items - 1, memo))