0/1 Knapsack

Explore the 0 1 knapsack problem where you maximize the value of items within a weight limit. Learn to apply dynamic programming with constraints that items cannot be split or repeated, enhancing your problem solving skills for coding interviews.

We'll cover the following...

Statement
Examples
Understand the problem
Figure it out!
Try it yourself

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:

An item may not be broken up to fit

...