0/1 Knapsack - DP

"""
This function knapsack takes the weights and values of the items, as well as the capacity of the knapsack, 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.
- dp[i][w]: Represents the maximum value that can be obtained using the first i items with a knapsack capacity of w.
- The algorithm uses a 2D list dp where dp[i][w] represents the maximum value that can be obtained with the first i items and a knapsack capacity of w. The solution builds up this table iteratively, using the property that the optimal solution to a problem can be constructed from the optimal solutions to its subproblems.
"""

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][capacity]

# Example usage:
weights = [1, 2, 3, 4]
values = [1, 2, 5, 6]
capacity = 7
max_value = knapsack(weights, values, capacity)
print(f"Maximum value in knapsack: {max_value}")