Understanding the 0/1 knapsack pattern

A large family of problems hands us a set of items and a single capacity, and asks us to pick the subset of items that does the best within that capacity. Filling a bag of fixed weight capacity with the most valuable items, or choosing the projects that fit a fixed amount of money while maximising the total return, are both problems of this kind. Every item is either picked or left behind, each item can be used at most once, and the total the chosen items consume must stay within the capacity.

Problems like these are solved by the 0/1 knapsack technique, where we decide the items one at a time and, for every possible amount of remaining capacity, record the best answer so far. The "0/1" in the name says that every item is taken whole (1) or not at all (0), and once an item is decided we never return to it.

The input is a set of n items given as two arrays, weights and costs, where the item at index i carries a weight weights[i] that says how much of the capacity it consumes, and a cost costs[i] that says what it adds to the answer. Along with the items we are given a single capacity C, the limit that the chosen weights may not exceed.

Because for every possible amount of remaining capacity, each item is decided once, the subproblems lay out over two axes, the item being decided and the capacity still available.

In this lesson we will learn the 0/1 knapsack technique, why it qualifies as a dynamic programming problem, and how to solve it both top-down and bottom-up.