Identifying the 0/1 knapsack pattern
The 0/1 knapsack pattern solves problems where the input is a set of items and a single budget, and the answer comes from choosing a subset of the items, with each item taken at most once. These are generally medium problems where we iterate through the items once, and at each item we decide between taking it and skipping it using answers we have already computed for the remaining items and budgets.
When a problem statement, or its natural recursive solution, fits the template below, it is a 0/1 knapsack problem.
Given
n items and a budget C, compute dp(i, c), the optimal (opt) value obtainable using the items [0..i] with c budget remaining, for each item 0 <= i < n and remaining budget 0 <= c <= C. For each item you either skip it or take it, each choice combining (⊕) its cost with the value of the state it leads to, and dp(i, c) is the opt of those two choices.How to identify the 0/1 knapsack pattern
There are two signals that tell us a problem fits the 0/1 knapsack pattern.
A set of items and a single budget
If the input is a collection of items where each item consumes a part of one shared budget, a capacity that must not be exceeded or a target that 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 0/1 knapsack problem.
A set of items drawing on one budget reduces to a single value.
Liking the course? Check our discounted plans to continue learning.