Understanding the bounded knapsack pattern

A large family of problems hands us a set of items, each available in a limited number of copies, and a single capacity, and asks us to pick the copies that do the best within that capacity. Filling a bag of fixed weight capacity with the most valuable items when the store holds only a few copies of each, or paying an exact amount from a purse that holds a limited number of each coin, are both problems of this kind. Every item can be taken several times but never more than its own limit, and the total the chosen copies consume must stay within the capacity.

Problems like these are solved by the bounded 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 "bounded" in the name says that every item comes with its own copy cap, so an item can be taken anywhere from 0 times up to its cap, and once an item is decided we never return to it.

The input is a set of n items given as three arrays, weights, costs, and counts, where the item at index i carries a weight weights[i] that says how much of the capacity one copy consumes, a cost costs[i] that says what one copy adds to the answer, and a count counts[i] that says how many copies of it are available. 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 bounded knapsack technique, why it qualifies as a dynamic programming problem, and how to solve it both top-down and bottom-up.