Video 3-2: Knapsack

0:04 In the next subsection, we'll see one concrete example for a problem that is in general empty heart but admits such a pseudo polomial time algorithm. Uh which indeed um has has practical uh value because sometimes in these problems the integers that occur are indeed not too big. Uh that's the mapsac problem. So just to recap um we've seen the decision version the optimization version is given here again we have these items one up to n and what we're given is the weights which is um negative thing if you want and then values which is the positive thing and some capacity and you're trying to select a set of items items t so that uh their total weight is at most B. They fit into your knapsack is also called the burglar problem. You're breaking into a house and you're trying to take as many valuables as you can fit in your backpack before you have to run. But if your backpack's too heavy, you can't run fast enough. Uh let's stay with the more neutral formulation. So you just take items of total weight at most speed that you want to maximize the value you get for them.

1:32 Okay, let's recap what dynamic programming is just to put that in in context. This is mostly for uh people that seen this template in efficient algorithms. A reminder if you've seen dynamic programming somewhere else then you may have seen it in slightly different terminology. Uh the essence of dynamic programming is to break a problem into small sub problems that you exhaustively solve but where you can reuse solutions of sub problems to stitch together a solution for a bigger problem. And then there's um the the the bottom three steps are very mechanic. They're always the same. So just in this concrete example uh for for the knapsack problem what we can use as sub problems is restricting to the first n prime items. Instead of allowing all of them we just look at a prefix of the items and we also restrict the weight to be potentially less than the total weight we are allowed in the end.

2:37 And then um at each point in time we'll make a guess whether or not we include this last uh item that we're allowed now. And that will be enough to write down a recurrence. So let's let's do that together. V stands for value. It's going to be the maximum value you can get in this sub problem. Meaning you can only pick items up to position N prime. you're only allowed the first items and the weight is further restricted not B but B prime um so we need some base cases let's see if I can fit that here [Music] um we can do the idiotic base case when uh n prime is zero and I'm not allowed any items then the maximum value has to be zero. [Music] Um that might be all base cases we need really. Let's see. If we allowed one item, at least one, then there's uh those two n prime fits in our knapsack then we have the option of taking it if it's too big then we don't even have this option let's do the simple version first and then this will be the more interesting case so if the item n prime cannot fit in the best I can do is to use any of the previous items And I'm now still at full capac. I can take the same capacity. It doesn't matter. Now, if I can fit this last item, I have two options. I can pick the best of two uh traces. So, I'm doing a maximum. And one option is uh the same as above. I'm not picking this new item that I'm allowed now.

5:11 So again this option but here I have the second choice of picking this new item. So I get the value for n prime. But then for the rest of the items I only have b prime minus the weight of this. So I have a smaller um leftover capacity. Uh I have a smaller leftover capacity whatever is left after putting this item in. But I get the value for this item. With this recurrence, the final answer will just be in the original um problem where I'm allowed all items and the full capacity. And you can recursively fill those. Um this is the point where it makes a difference. If you've seen DP before you'll say yeah I know I can take it from here. Um there's a bottomup algorithm to uh fill the table of all those V entries and I know how to back trace and you can reconstruct the solution. Uh if none of this makes sense um then uh suffices to say that you can you can evaluate this recursion and whenever you uh use a value recursively, you store it in a in a lookup table so that you're never computing the same value again. Which means um you're only going to spend constant time evaluating any of these options when you first uh you first evaluate them.

6:57 Now constant time is the number of arithmetic operations. Uh on a Turing machine it would be log max in time. So let's analyze the the running time. So to compute these these option in particular compute the max and the plus in because these are numbers uh with that many bits and you have to add them up on a touring machine. We're in this logarithmic cost model. Uh, that's for one of these entries. And the number of entries in the matrix is the overall number of items. And the overall number of entries for the second component is the budget. And now the number of items can be bounded in terms of the size um of the input. But B is a is a number that I'm specifying in the input. Right? N is bounded the the items are bounded by the input size because I have to list the number for each of them. So I need to spend at least n bits to specify n items. But for this number b the capacity of my knapsack this I can just write down as a binary number. So this will be another factor and here it's just max in that's the best we can say in in general. So in particular this is the pseudo polomial part that we have to fill this table for all possible capacities between zero and [Music] b. All right. Uh here's summed up what I've uh briefly sketched the running time for this dynamic programming algorithm. Um is polomial in the input size and max and so it's a pseudo polomial algorithm but you may also know that the napsac problem in general is np heart.

9:32 So it is one of those cases where we shouldn't expect a polomial time algorithm. um but a pseudo polomial algorithm is possible. This is one concrete example where this this theory seems to have value and if indeed your capacities are small then uh that's good. Um also let me point out this is a bit uh pessimistic in that sense that we don't care what how big the values are. is only the weights that matter. They're the capacity of the knapsack. If the values are big, that's not a problem. We just compute with them and add them up. The capacity is what blows up the space of this dynamic Just to stress that point that might be in an application this might make a difference. Now we've seen one concrete example. You can apply a very similar trick to some other problems which admittedly are somewhat similar to NAPSAC. Uh there's the partition problem. Remember these are numbers. Can you uh assign them to two camps so that their sum is equal or um making change if you uh have coins and you're trying to give the smallest number of coins to make a certain total uh finding the minimum number of coins is empty hard but can be solved with such a pseudo polinomial algorithm but they also have um a similar flow rate to this to this laps problem. Uh there's for other problems uh even if they're integer input problems it seems you cannot do such an algorithm and there's a little bit of theory to suggest why that is indeed not possible.