Understanding the unbounded knapsack pattern

A large family of problems hands us a set of items and a single capacity, and asks us to fill that capacity with copies of the items in the way that does the best with the constraint that every item can be picked an unlimited number of times. Calculating change for an amount with the fewest coins, or cutting a rod into priced pieces for the best revenue, are both problems of this kind. Every item can be taken any number of times, the items come in unlimited supply, and the total the taken items consume must fill the capacity.

Problems like these are solved by the unbounded knapsack technique, where we solve the capacities one at a time and, for every possible amount of remaining capacity, build the best answer from the answers at smaller capacities. The "unbounded" in the name says that no item is ever used up, taking an item leaves the whole item set available again.

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 target that the chosen weights must fill.

Because every item comes in unlimited supply, taking an item leaves the whole set available again, so the only thing that changes between subproblems is the remaining capacity, and the subproblems lay out along a single axis, the capacity still available.

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