The bottom line of this thought experiment, the deliverable will be a recurrence. And we're going to arrive at the sub problems for the knapsack problem just as we did for max weight independent sets by doing a thought experiment about the optimal solution, and understanding what it has to look like in terms of solutions to smaller subproblems. Remember, the key to any dynamic programming solution is to figure out what is the right set of subproblems. So let's now execute a recipe for developing a dynamic programming algorithm. So you can imagine how it would come up in a lot of contexts. Really, just whenever you have sort of a budget of a resource that you can use, and you want to use it in the smartest way possible, that's basically the knapsack problem. This problem comes up quite a bit, especially as a subroutine in some larger task. But that would really be doing a disservice to this problem which is actually quite fundamental. Now I could tell you some cheesy story about a burglar breaking into a house with a knapsack with a certain size capital W and wants to make away with sort of the best loot possible. So what prevents us from picking everything? Well, the sum of the sizes of the items that we pick have to total to at most the capacity capital W. What do we want? We want as much value as possible, so we want to maximize the sum of the values of the items that we select. The knapsack problem, the responsibility of an algorithm is to select a subset of the items. The role of these integrality assumptions will become clear in due time. In addition to these two n numbers, we are given one more which is called the capacity, capital W, again we'll assume this is non-negative and an integer. We're going to assume that both of these are non-negative, for the sizes we're going to make additional assumption that their integral. So each item comes with a value, V sub i, the more the better for us, and also a size, W sub i. So let's jump right into the definition of a knapsack problem.

And we'll show how following the exact same recipe that we used for computing independent sets in path graphs leads to the very well known dynamic programming solution to this problem.

It's to a quite well known problem, it's called the knapsack problem. So in these next two videos we'll give our second application of the dynamic programming paradigm.

Knapsack problem example