Identifying the bounded knapsack pattern
The bounded knapsack pattern solves problems where the input is a set of items and a capacity and the answer comes from choosing some copies of each item to take, with each item taken at most its own limited number of times. These are generally medium problems where we iterate through the items once, and at each item we decide between its copy counts using answers we have already computed for the remaining items and capacities.
When a problem statement, or its natural recursive solution, fits the template below, it is a bounded knapsack problem.
Given
n items and a capacity C, where the item i can be taken up to counts[i] times, compute dp(i, c), the optimal (opt) value obtainable using the items [0..i] with c capacity remaining, for each item 0 <= i < n and remaining capacity 0 <= c <= C. For each item you choose how many copies k to take, from 0 up to its cap, each choice combining (⊕) its cost with the value of the state it leads to, and dp(i, c) is the opt of those choices.How to identify the bounded knapsack pattern
There are two signals that tell us a problem fits the bounded knapsack pattern.
A set of items and a single capacity
If the input is a collection of items where each item consumes a part of one shared capacity, a target that must not be exceeded or must be hit exactly, and the goal is to reduce the whole collection to a single value, like an optimum, a count, or a yes or no, the problem is generally a knapsack problem.
A set of items drawing on one capacity reduces to a single value.
Liking the course? Check our discounted plans to continue learning.