This note is an introduction to the important algorithmic concept of dynamic programming, written the way I’d present it in one of my classes. Information on dynamic programming and the 0-1 knapsack example are readily available everywhere, of course, but I have a hard time finding presentations with an approach and level of complexity that I like. This is my effort at filling that gap for my students.
Overview
Dynamic programming is awesome. It’s an important building block of many advanced algorithms, including shortest paths and genetic sequence alignment. It also shows up frequently in whiteboard interview questions and competitive programming problems. It is, however, one of the trickier algorithm concepts to master.
The method was formalized by Richard Bellman of the RAND Corporation1 in the 1950s. The term “programming”, in those days, was often used to refer to solving mathematical optimization problems, as a synonym for “planning”. It’s said that Bellman picked the name “dynamic” in part because he just thought it sounded cool.
As we’ll see, the basic strategy of dynamic programming is to take a high-level problem, decompose it into one or more subproblems, and then find the optimal solutions to those subproblems recursively. That’s similar to other divide-and-conquer algorithms like Quicksort. The major distinguishing element of dynamic programming is avoiding the overhead of a purely recursive solution by using a table to keep track of the subproblem solutions, so that each problem only needs to be solved one time.
This note is going to discuss:
The 0-1 Knapsack Problem, one of the canonical dynamic programming problems
The guiding strategy for designing DP algorithms: isolate one decision, reason about its cases, then optimize what’s left
Recursive solution to the 0-1 Knapsack Problem
A better bottom-up approach that solves the problem without using recursion
A second example that illustrates the same principles: the rod-cutting problem
But before we talk about that, let’s talk about a game show from the 90s.
Supermarket Sweep
Supermarket Sweep is a game show that first aired in 1965 and has been revived numerous times on different networks since then. If you’re an older millennial like me, you might remember it from those times you stayed home sick from school and got to chill on the couch all morning watching daytime TV shows.
The basic format consisted of two segments. In the first part, contestants (as teams of two) answered quiz questions; correct answers earned time on a clock. The second part was the titular sweep, where each team would get to use their accumulated time to tear through a soundstage set up like a grocery store, filling their shopping cart with items. The team that swept up the combination of items with the highest overall value was the winner.
Here’s video of the 1990s version of the show. The contestants with the most time enter the shopping area first, with the other shoppers entering as the clock ticks down. It’s wonderfully chaotic.
Watch the video. Before continuing, pause and think for a second:
What’s a good strategy for the sweep? What items should a shopper prefer to grab and which ones should she skip?
If you watch the video, you’ll see that Kristina, the first shopper, heads immediately for the meat aisle and starts filling her cart with beef, hams, and turkeys. This illustrates the basic strategy all the shoppers follow: You only have a limited amount of space in each cart, so you should fill it with the highest-value items possible.
Turkeys and other big cuts of meat are large, but carry the highest values so they’re worth it. Other high-value items would be things like fancy coffees and cheeses that also have the benefit of not taking a lot of space. Paper towels, on the other hand, would take up a lot of cart space for only low value.
If you wanted to be a huge nerd about this (which you do), you could think of the basic problem of filling the shopping cart as a constrained optimization problem.
The cart has a fixed maximum capacity.
There is a large selection of items you can take. Adding an item to your cart awards you its value, but consumes some of your capacity.
Items can’t be subdivided or split, you have to take the whole or none. In the real show, contestants could only take at most five of each item.
Therefore, the goal is to maximize the value of items taken, subject to constraints on the total capacity of the cart, the requirement to take whole items, and the upper limit five on each.
Knapsack Problems
The Supermarket Sweep challenge is a specific version of the general class of knapsack problems, all of which involve selecting items with the goal of obtaining the highest possible value subject to constraints on what and how much you can take2.
The canonical knapsack problem, the grandaddy of them all, is the 0-1 Knapsack Problem. Its fundamental constraint is that you are restricted to taking either one or zero of each item — you can’t take fractions of an item, nor can you take multiples.
0-1 Knapsack belongs to the field of combinatorial optimization, which is concerned with how to select the best possible combinations of things. It is in fact a very important algorithmic building block, because combinatorial optimization problems show up in all kinds of real-world applications related to resource allocation.
Use an LLM research tool to search for real-world applications of combinatorial optimization and the knapsack problem.
The Supermarket Sweep challenge allowed contestants to take up to five copies of an item. That would be known as a bounded knapsack problem, where the problem specifies an upper bound on the number of items you can take.
For the rest of this note, we’re going to look at the 0-1 knapsack specifically. It’s the most important problem of its type and the solution to most other knapsack variations can be thought of as variations on the basic 0-1 technique.
First example and solutions that don’t work
Let’s look at a concrete example. Suppose we have the following problem. The goal is to take combination of items having the greatest value without exceeding the weight limit.
Weight limit = 10
Item Weight Value
---- ------ -----
1 2 10
2 3 12
3 5 25
4 6 36What is the optimal combination of items in this example?
The optimal combination is to take items 2 and 4, for a total weight of 9 and value of 48.
Notice that this doesn’t use the entire capacity, but that’s perfectly fine. Taking items 1, 2 and 3 would give a weight of 10, but a value of only 47.
Trying all combinations
What if you wanted to find the solution in a structured way? A first thought is to just try brute force: test all possible combinations of items and identify the one with maximum value that meets the weight constraint.
What’s the problem with this approach?
Thinking about the complexity should quickly convince you that testing all combinations of items is infeasible in general.
Each possible solution assigns a value of 0 (not taken) or 1 (taken) to each of the n items. This is the same as generating all bit strings of length n, of which there are 2n. Therefore, testing all possible solutions is exponential in n. This isn’t a problem if n is small — four items have only 16 possible combinations — but exponential growth will quickly crush you beyond perhaps 20-30 items3.
A greedy approach
“But wait!”, you say. “I can do better with a greedy approach! Let’s sort the items by value / weight and then take them in that order. This will guarantee that I’m always gaining the most value for each unit of weight I place in the knapsack.”
Try that approach on the example problem. What solution do you obtain? Is it optimal?
Adding a new column for value / weight to the table:
Weight limit = 10
Item Weight Value Value / Weight
---- ------ ----- --------------
1 2 10 5
2 3 12 4
3 5 25 5
4 6 36 6We first take item 4 with a ratio of 6. This leaves four units of capacity, so we next take item 1, which has a ratio of 5 and fits in the knapsack (skipping item 3 because it can’t fit with item 4). The total value is 46, which isn’t as good as the actual optimal of 48!
Sorting by value-to-weight ratio therefore isn’t guaranteed to find the optimal solution to a 0-1 knapsack problem. It would be optimal, however, for the fractional knapsack problem, where the items are treated as infinitely divisible (like liquids or fine powders). In that case, the value-to-weight strategy would take all of item 4 followed by four units drawn — in some mixture — from items 1 and 3. The resulting combination has a score of 56.
Formalization
Breaking it down more formally,
There is a collection of n items. Remember that we’re dealing with an abstract problem here, so these “items” could represent anything that we’re interested in. They don’t necessarily have to be real physical things like groceries.
The knapsack has a maximum weight capacity of W, where “weight” is a general term for whatever quality we’re using to restrict how much we can take.
Each item i has a weight that we’ll denote wi and a value that we’ll denote vi . Again, think about “weight” and “value” being defined in whatever specific way makes sense for the problem.
For each item i, there’s a decision variable xi that specifies whether we take item i or not. These variables are either 0 or 1.
Writing it out as a formal optimization problem, it would look like this4:
Take a moment to look at the problem notation and verify that the mathematical version matches the written description.
The Dynamic Programming Approach
So let’s consider our situation: We have a combinatorial optimization problem where we need to select from a collection of n items. Testing all possible solutions is not feasible, and there’s no obvious greedy strategy that will allow us to solve the problem using sorting.
It’s time to use dynamic programming.
The essence of dynamic programming is that finding the overall optimal solution to a problem can often be expressed in terms of the optimal solutions to one or more subproblems.
This may sound familiar. We’ve already seen examples of a similar approach through divide-and-conquer algorithms like Quicksort and merge sort: split the top-level problem into smaller subproblems, divide those into subproblems, and so forth, until you reach a simple base case, then build back up to the top-level solution. The sorting algorithms, like most divide-and-conquer approaches, are recursive.
If you need a refresher, review the divide-and-conquer sorting algorithms.
Dynamic programming adds the idea of optimality to the divide-and-conquer framework — in general, any problem language that asks for “the optimal solution” is often a good clue that dynamic programming might be involved5.
There are two main challenges in designing dynamic programming solutions:
It’s not, by itself, a solution to any particular problem. Instead, DP is a general strategy for designing solutions. Deciding to use dynamic programming still requires you to work out how to divide the top-level problem into subproblems.
Although DP solutions might be formulated recursively, the straightforward recursive implementation is often inefficient. As we’ll discuss, most problems can instead be solved by working bottom-up.
Strategy: Isolate one decision, then think about what’s left
Let’s work through the dynamic programming solution to 0-1 knapsack, which will illustrate the principles involved.
Our goal is to decide whether each of the n items should be included in the solution or excluded. Rather than trying to consider combinations of items together, let’s imagine that we want to solve this by making a series of decisions that consider one item at a time.
This is a good starting point for devising a dynamic programming algorithm: consider one decision variable, reason about each of its cases, then optimize the subproblems that result in each case.
Consider the example problem from earlier:
Weight limit = 10
Item Weight Value
---- ------ -----
1 2 10
2 3 12
3 5 25
4 6 36Think about just one item — item 4, let’s say. There are two options:
If item 4 is included in the optimal solution, then it contributes a value of 36 and takes 6 units of weight. The optimal solution is therefore 36 plus the best result we can obtain from the remaining n - 1 items using 4 units of weight.
If item 4 is excluded, then we gain no value from it but lose no capacity. The optimal result is the best we can obtain from the other n - 1 items using the full 10 units.
Notice: In both cases, the result is a subproblem defined over n - 1 items. This is the key to dynamic programming! The optimal solution to the full problem of size n depends on the optimal solutions of smaller subproblems.
Go back and read that section again. Make sure you’re comfortable with how the two subproblems were derived by considering the cases for just one decision variable.
Theorists use the term optimal substructure to describe this property.
Recursive solution
Armed with this insight we can design a general approach to the first solution. Suppose we have a function called
knapsack(n, c, weights, values)that calculates the optimal solution for items 1 to n using a capacity of c and the given arrays of the weights and values of the items.
By the reasoning given for the example problem, we can consider either including or excluding item n by itself to obtain two subproblems over items 1 to n - 1.
If we include item n, the optimal result is
values[n] + knapsack(n - 1, c - weights[n], weights, values)The first term is the value we obtain from item n. The second is the optimal solution to the subproblem over the remaining n - 1 items with reduced capacity.
If we don’t include item n, the optimal solution is simply
knapsack(n - 1, c, weights, values)That is, it’s the optimal solution to the problem over items 1 to n - 1 with no loss of capacity.
To determine the true optimal solution, calculate both and take whichever is larger. This gives the recursive definition of the knapsack function:
// Recursively solve subproblems and return optimum
knapsack(n, c, weights, values) = max (
// Case 1: item n is included
values[n] + knapsack(n - 1, c - weights[n], weights, values),
// Case 2: item n not included
knapsack(n - 1, c, weights, values)
)That’s the core of the method, but there are a couple of other details to consider.
First, we need to check that there’s sufficient capacity to hold an item before we consider it. If we can’t hold item n, skip it and continue to the remaining items.
// If item n can't fit, skip it and continue to the other items
if (weights[n] > c) {
return knapsack(n - 1, c, weights, values)
}Second, we need to define the base case that makes the recursive function calls stop.
What should the base case be? Think about the values of both n and c.
There are two base cases:
If n = 0, in this formulation, then there are no items to consider6
If c = 0, then there’s no remaining capacity, so we can’t include any items
In both cases, the appropriate result is to return 0 — if you have no items or no capacity then you can’t obtain any value.
Putting all that together, we arrive at a recursive solution to the 0-1 knapsack problem. Here’s an implementation in vaguely Java-ish pseudocode.
/**
* Recursive 0-1 knapsack problem
*/
knapsack(n, c, weights, values) {
// Base case: nothing to consider
if n == 0 or c == 0 {
return 0
}
// If item n can't fit, skip it and continue to the other items
if weights[n] > c {
return knapsack(n - 1, c, weights, values)
}
// Main case: recursively solve subproblems and return optimum
return max (
// Case 1: item n is included
values[n] + knapsack(n - 1, c - weights[n], weights, values),
// Case 2: item n not included
knapsack(n - 1, c, weights, values)
)
}Bottom-up solution
Is the recursive solution good? Well, it seems reasonable and the code is not that hard to implement. However, it turns out that solving the problem recursively is not actually necessary.
The recursive function a top-down solution: it starts with the complete problem over all n items with the full capacity and works its way down to the base cases. This might result in visiting some subproblems multiple times. An alternate approach is the bottom-up solution: start with the bases cases and build up to the top-level result, which guarantees that we only need to solve each possible subproblem once.
Suppose that we have the example problem from above, with four items and a capacity of 10.
Weight limit = 10
Item Weight Value
---- ------ -----
1 2 10
2 3 12
3 5 25
4 6 36Create an 11 x 5 table that includes an entry for each value of n and capacity c, plus rows and columns for the base cases of 0.
capacity c
| 0 1 2 3 4 5 6 7 8 9 10
------------------------------------------------
0 |
1 |
max item n 2 |
3 |
4 |Each column corresponds to a capacity level from 0 to 10. The rows indicate the maximum item we’re allowed to consider. Row 2, for example, corresponds to solutions that can use items 1 and 2, but not 3 and 4.
Each entry in the table records the optimal result for one combination of n and c. The overall solution is the entry in the lower-right corner for n = 4 and c = 10 — that is, the optimal solution if we’re allowed to consider all four items with a capacity of 10.
We’re going to fill in the table from the upper-left to the lower-right. Start by filling in the row and column for 0, which correspond to the base cases of no items to consider (n = 0) or no capacity to fill (c = 0).
capacity c
| 0 1 2 3 4 5 6 7 8 9 10
------------------------------------------------
0 | 0 0 0 0 0 0 0 0 0 0 0
1 | 0
max item n 2 | 0
3 | 0
4 | 0The pseudocode below assumes that we can initialize the table and fill in the base cases. It then works from the upper-left to the lower-right, filling in the entries using the same rules as the recursive solution. Notice: the solutions to every subproblem are stored in the table! Therefore, we never need to solve a subproblem more than once and each new solution depends only on entries that have already been solved and filled in.
/**
* Bottom-up knapsack solution
*/
Initialize table
Fill in base cases for n = 0 and c = 0
// Iterate over all other table entries
for n = 1 to 4 {
for c = 1 to 10 {
// Item n doesn't fit in capacity c
if weights[n] > c {
table[n][c] = table[n - 1][c]
}
// Default: choose max of the two subproblem entries
else {
table[n][c] = max (values[n] + table[n - 1][c - weights[n]],
table[n - 1][c])
}
}
}Compare the bottom-up iterative solution to the top-down recursive solution and verify that they use the same subproblems.
Now let’s start filling in the table using the method.
What values should go in the row for n = 1?
Row 1 contains the subproblems where we’re allowed to consider only item 1. There are only two options here: if we have enough capacity, take item 1, otherwise we have to leave the knapsack empty. The result is the following:
capacity c
| 0 1 2 3 4 5 6 7 8 9 10
------------------------------------------------
0 | 0 0 0 0 0 0 0 0 0 0 0
1 | 0 0 10 10 10 10 10 10 10 10 10
max item n 2 | 0
3 | 0
4 | 0Beginning to fill in row 2, we see similar behavior. Once we have a capacity of 3, the best option is to take item 2.
capacity c
| 0 1 2 3 4 5 6 7 8 9 10
------------------------------------------------
0 | 0 0 0 0 0 0 0 0 0 0 0
1 | 0 0 10 10 10 10 10 10 10 10 10
max item n 2 | 0 0 10 12 12
3 | 0
4 | 0What about position (2, 5)? By the solution method,
table[2][5] = max(12 + table[1][2], table[1][5])Checking the table, we see that the first choice is the best: capacity 5 allows us to take both of the first two items for a score of 22. The same behavior continues across row 2.
capacity c
| 0 1 2 3 4 5 6 7 8 9 10
------------------------------------------------
0 | 0 0 0 0 0 0 0 0 0 0 0
1 | 0 0 10 10 10 10 10 10 10 10 10
max item n 2 | 0 0 10 12 12 22 22 22 22 22 22
3 | 0
4 | 0Continue filling in the table.
Here’s the final version. Notice that the lower-right entry contains the final answer.
capacity c
| 0 1 2 3 4 5 6 7 8 9 10
------------------------------------------------
0 | 0 0 0 0 0 0 0 0 0 0 0
1 | 0 0 10 10 10 10 10 10 10 10 10
max item n 2 | 0 0 10 12 12 22 22 22 22 22 22
3 | 0 0 10 12 12 25 25 35 37 37 47
4 | 0 0 10 12 12 25 36 36 46 48 48Again, take a moment to check a few table relationships. For example, you can verify that
table[4][10] = max(36 + table[3][4], table[3][10])Complexity
What’s the complexity of the bottom-up method? Suppose that we have n total items to consider and a maximum weight capacity of W. The size of the table is
(n + 1)(W + 1)
The running time is dominated by the loops that fill in the table, which take nW total iterations. Each iteration checks a fixed number of other table entries, so the time per iteration is constant and the overall complexity is O(nW) — that is, the running time of the method is proportional to the number of entries in the table.
Most complexities we’ve seen up to this point have been a function of one variable, which is usually the size of the input. The bottom-up solution is an example of an algorithm where the complexity is controlled by two independent parameters.
Optional aside: Pseudo-polynomial complexity
Theorists would say that the bottom-up solution has "pseudo-polynomial" complexity. This is a bit technical and refers to the distinction between the value of an input and its length as encoded in digits or bits.
Consider doubling the value of n. Doing so corresponds to doubling the number of rows in the table, which doubles the time required to run the method. Likewise for scaling W by a constant factor. This appears to be polynomial.
However, suppose you write down the value of n in digits, then add just one additional digit; for example, going from a value of 10 to 100. This is only a constant increase in the input length, but it increases the size of the problem by a factor of 10. Similar reasoning applies if we consider n to be encoded as a sequence of bits, which it would be in a real computer. Each single bit added to the input string corresponds to doubling the size of the problem.
This is the characteristic of pseudo-polynomial algorithms. They appear to be polynomial in the value of the numeric input parameter, but increasing the length of the input as digits or bits makes the problem size grow exponentially.
Another example: the rod-cutting problem
This is the first example in the dynamic programming chapter of Introduction to Algorithms by Cormen et al., the classic graduate-level algorithms textbook. It’s representative of problems that involve material handling and resource allocation.
We’re given a long steel rod and need to cut it into pieces to be sold. The sale price of a piece depends on its length in a nonlinear way. We’d like to find the division of the starting rod into pieces that maximizes their total sale value.
For example, suppose that the starting rod has a length of 7 and the sale prices for the different piece lengths are as follows:
Starting length = 7
piece length sale price
------------ ----------
1 1
2 3
3 5
4 5
5 7
6 8
7 10 The optimal solution is to cut lengths of 3, 3, and 1, which will sell for a total of 11.
Recursive solution
As we said earlier, the requirement to find the optimal solution is a clue that dynamic programming might be involved.
Think about the basic strategy that we used for the 0-1 knapsack problem: consider one decision variable, reason about each of its cases, then optimize the subproblems that result in each case.
What’s the basic choice that we should consider?
For any division of the rod, there must be a first cut. Let’s reason about the options that we have for the length of the first piece, then think about how to optimize what remains. Suppose the entire rod has length n.
The first piece can be any length from 1 to n.
If the first piece is of length i, we obtain the value for a piece of that length.
The remaining rod has length n - i. To maximize its value, we should then cut this length optimally. This is another instance of the rod-cutting problem!
Putting that together, the basic recursive solution is:
/**
* Recursive implementation of the rod cutting problem
*/
rod_cutting(n, values) {
// Base case: nothing to consider
if n == 0 {
return 0
}
// Keep track of the best solution
overall_best = 0
// Recursive case: consider the first piece
for cut = 1 to n {
// Recursively calculate optimal value for this starting cut
best_for_this_cut = values[cut] + rod_cutting(n - cut, values)
// Update the overall best if necessary
best = max(overall_best, best_for_this_cut)
}
return overall_best
}Although the details are different, notice how this solution has the same basic form as the 0-1 knapsack solution. Consider the choices for one decision, then determine the overall value of each choice by solving a subproblem.
Bottom-up solution
The pure recursive solution also suffers from the same problem as the knapsack: it will repeatedly solve the same subproblems over and over again. The bottom-up solution is more efficient and requires allocating only a single array from 0 to n.
Suppose that we want to solve the example problem with a starting length of 7. Allocate an array with entries for lengths from 0 to 7, where 0 is the base case.
Starting length = 7
subproblem length optimal solution
----------------- ----------------
0 0
1
2
3
4
5
6
7The optimal solution to each subproblem depends on only the previous entries in the table.
/**
* Bottom-up rod cutting solution
*/
initialize solution array
// Fill in the array from bottom to top
for i = 1 to n {
// Consider all subproblems less than i
for cut = 1 to i {
solution[i] = max(solution[i], values[cut] + solution[i - cut]
}
}
// The overall optimal solution
return solution[n]Work through the example problem and fill in the array.
Here’s the complete solution. For the first few entries:
A rod of 1 has only one option, which is to leave it intact for a value of 1
A rod of length 2 has a value of 3, which is better than the value of cutting it into pieces of 1 and 1
Likewise, a rod of 3 is better than cutting into 1 and 2
A rod of 4 is best broken into two pieces, either as 1 and 3 or as 2 and 2; both options have a value of 6
Starting length = 7
subproblem length optimal solution
----------------- ----------------
0 0
1 1
2 3
3 5
4 6
5 8
6 10
7 11What’s the complexity of this bottom-up solution?
The method has a nested-loop structure. The first iteration considers only one cut option, the second consider two, and so forth. The total number of iterations is
which is O(n2).
Summary
Dynamic programming is an essential algorithmic building block, so learning how it works will help you tackle tricky problems. As you’re working through these notes, keep the following ideas in mind:
Many DP algorithms are, conceptually, “optimization + recursion”. We want to solve an overall optimization problem and do that by recursively finding the optimal solutions to one or more subproblems.
The strategy of isolating one decision, considering its options, and then thinking about the resulting subproblems is often a good strategy to begin designing a solution.
The bottom-up technique is the preferred solution approach. It only needs to evaluate each subproblem one time, so its complexity is bounded by the size of the table.
In addition to being an important problem in its own right, understanding the details of the 0-1 knapsack problem will carry over to other dynamic programming and combinatorial optimization problems.
Practice questions
0-1-2 knapsack
Modify the knapsack solution to allow for taking 0, 1 or 2 of an item, but not more. Tip: think about how taking two of an item changes the recursive relationship. How much value do you obtain and how much capacity remains for the subproblem?
Subset sum
You’re given an array of integers (each of which might be positive or negative) and a target value T. Design a method to verify if a subset of the integers sums to exactly T.
For example, if the array is
[2, 3, 5, 7, 11, 13]and the target is 20, the answer is True because 2 + 7 + 11 sums to 20. Note that more than one solution is allowed; 7 + 13 would also be a valid subset.
Tips:
Sometimes things that seem different are almost the same. This feels very similar to the 0-1 knapsack, but it’s a decision problem, not an optimization, so the result must be boolean True or False.
Suppose you’re considering the last item, the 13. There are three possibilities:
13 by itself is the target. You can return True immediately.
13 is not the target but is included in the sum. In this case, you need to check the other items to see if you can find a subset that adds to T - 13.
13 is not included in the sum. In this case, check the other items for a sum of T.
Use these ideas to write down the recursive relationship and base cases, then work out a bottom-up strategy for solving the problem.
A major Cold War-era think tank and research organization.
“Knapsack” is an old-time term for a backpack.
It is possible to do better with a structured search approach, which could prune paths to avoid wasting time generating combinations that can’t be feasible — backtracking search would do this. There are also techniques like genetic algorithms and simulated annealing that can explore the solution space in heuristic ways; these can be effective if you want a quick way to find a good solution that might not be optimal. Maybe we can talk about those later.
This is the same notation used in the Wikipedia article.
But not a requirement. There are dynamic programming problems that involve making decisions or counting rather than optimizing, but the optimization framing is the best way for us to approach the method.
Note that we’re using 1-based indexing because of how the problem has been formulated. If you wanted to implement it in a standard language, you’d set n < 0 as the stopping condition.