Identifying the unbounded knapsack pattern

The unbounded knapsack pattern solves problems where the input is a set of items and a capacity, and the answer comes from taking copies of the items, with each item taken any number of times. These are generally medium problems where we iterate through the capacities once, and at each capacity we decide which item to take using answers we have already computed for the smaller capacities.

When a problem statement, or its natural recursive solution, matches the template below, it is an unbounded knapsack problem.

Template

Given n items and a capacity C, compute dp(c), the optimal (opt) value obtainable that fills exactly the capacity c from all the items, for each remaining capacity 0 <= c <= C. At each capacity we can take each item an unlimited number of times, each choice combining (⊕) its cost with the value of the state it leads to, and dp(c) is the opt of those choices.

How to identify the unbounded knapsack pattern

There are two signals that tell us a problem matches the unbounded knapsack pattern.

A set of items and a single capacity

If the input is a collection of items, like coin denominations, piece lengths, or numbers, where each item consumes a part of one shared capacity, a target that must be hit exactly or filled in the best way, and the goal is to reduce the whole collection to a single value, like an optimum or a yes or no, the problem is generally an unbounded knapsack problem.

A set of reusable items drawing on one capacity reduces to a single value.