Solving the 0/1 Knapsack Problem

Statement

Suppose you have a list of weights and corresponding values for n items. You have a knapsack that can carry items up to a specific maximum weight, known as the capacity of the knapsack.

You want to maximize the sum of values of the items in your knapsack while ensuring that the sum of the weights of the items remains less than or equal to the knapsack’s capacity.

If all the combinations exceed the given knapsack’s capacity, then return $0$.

Note: While adding items in the knapsack, we either add the complete item or don’t add it. Moreover, we can’t add an item again that is already in the bag.

Let’s say you have a knapsack capacity of 5 and a list of items with weights and values as follows:

weights = [1, 2, 3, 5]

values = [10, 5, 4, 8]

There are four ways of storing items in the knapsack, such that the combined weight of stored items is less than or equal to the knapsack’s capacity.

• Item of weight 1 and weight 2, with a total value of 15.
• Item of weight 1 and weight 3, with a total value of 14.
• Item of weight 2 and weight 3, with a total value of 9.
• Item of weight 5, with a value of 8.

Though all of the combinations described above are valid, we need to select the one with the maximum value. Hence, we will select items with weights 1 and 2, as they give us the maximum value of 15.

Constraints:

• $1 \leq$ capacity $\leq 10^4$
• $1 \leq$ values.length $\leq 10^3$
• weights.length $==$ values.length
• $1 \leq$ values[i] $\leq 10^4$
• $1 \leq$ weights[i] $\leq$ capacity