Solution: 0/1 Knapsack

Statement

You are given $n$ items whose weights and values are known, as well as a knapsack to carry these items. The knapsack cannot carry more than a certain maximum weight, known as its capacity.

You need to maximize the total value of the items in your knapsack, while ensuring that the sum of the weights of the selected items does not exceed the capacity of the knapsack.

If there is no combination of weights whose sum is within the capacity constraint, return $0$.

Notes:

1. An item may not be broken up to fit into the knapsack, i.e., an item either goes into the knapsack in its entirety or not at all.
2. We may not add an item more than once to the knapsack.

Constraints:

• $1 \leq$ capacity $\leq 1000$
• $1 \leq$ values.length $\leq 500$
• weights.length $==$ values.length
• $1 \leq$ values[i] $\leq 1000$
• $1 \leq$ weights[i] $\leq$ capacity

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

A naive approach would be to generate all combinations of weights and calculate the profit of each combination. We would then choose the combination that yields the highest profit from among those that don’t exceed the knapsack capacity.

For example, suppose we’re given a knapsack with a capacity of $5$, and the following list of values and weights:

• values: $[3, 5, 2, 7]$
• weights: $[3, 1, 2, 4]$

To find the maximum profit, we try all possible valid combinations, that is, whose weight does not exceed $5$: