0/1 Knapsack - Recursive

"""
This recursive version of the 0/1 Knapsack problem works by considering two possibilities for each item:

1. Including the item in the knapsack.
2. Excluding the item from the knapsack.

It recursively evaluates these possibilities and returns the maximum value that can be obtained.

Explanation:

- weights: A list of weights of the items.
- values: A list of values of the items.
- capacity: The maximum weight capacity of the knapsack.
- n: The number of items considered.
- The function knapsack_recursive calculates the maximum value that can be obtained by either including or excluding the current item, and then moves on to the next item accordingly. This approach ensures that all combinations of included and excluded items are considered, and the optimal solution is found.
"""

def knapsack(weights, values, capacity, i):
    # base case: no items left or no capacity left. Capacity will never be negative here b/c of the ">=" check below.
    if i < 0 or capacity == 0:
        return 0

    # recursive case: either include the item or don't
    if capacity >= weights[i]:
        return max(
            knapsack(weights, values, capacity - weights[i], i-1) + values[i],
            knapsack(weights, values, capacity, i-1)
        )
    else:
        return knapsack(weights, values, capacity, i-1)

capacity = 7
weights = [1, 2, 3, 4, 5]
values = [5, 4, 3, 2, 1]
i = len(weights) - 1
print(knapsack(weights, values, capacity, i))