Video 3-3: Knapsack DP solution

0:03 Okay, let's do um a very short recap. We've been looking at the knapsack problem in the context of this uh chapter on pseudo polomial algorithms which were algorithms where the running time in a strict sense is exponential but it is polomial in a specific parameter of the input something that we will talk about in more detail in next in the next unit. uh namely the largest integer, the largest number that occurs in the input. And where did that discrepancy come from? Well, if you have an input that consists of numbers, you shall use a sensible encoding. And uh a sensible encoding is a binary code for the numbers say giving giving them in in base 2. And then a number of size n only takes roughly log n bits big of log n bits. By the way, even if you don't know how big the number is, right? There's Elias gamma codes and things like that. So even if you wanted to specify a number where you don't have to specify up front how many bits it takes, you can still do it in big O of login bits. You lose a factor two but not more. Uh so we can encode numbers if all we need is this numerical value very concisely, very succinctly.

1:23 On the flip side, this means if a problem consists of numbers that can be small written in small things, then taking time proportional to the value of the number is in principle exponential. But we call it pseudo polomial because it sometimes is closer to tractable. And one example was this knapsack problem. Uh the formal definition here uh again was was this one. We have items and different ones.

2:06 every centimeter counts. You have n items and you're trying to pick a subset and that subset has to satisfy a single constraint namely that it's its total weight is below a certain capacity threshold. So you can only take a certain number of uh weight in your in your knapsack. And with these items, you're trying to maximize the total value that they get. In principle, the value and the weight of an item could be totally unrelated. Of course, a typical special case is that they're even equal. Then it's just packing items and you try to um maximally fill your capacity. Uh but in general they can be completely disjointed or completely unrelated.

2:50 Um so let's see one concrete um problem instance how this uh can look like just to make sure we're on the same page. Uh so here's an example where you have four different items. They have a certain weight that's below that's the width of the box as well and you're trying to squeeze them in this box. And then they give you different value depending on whether you uh include them in your box or not. Okay. Um I think we might have exercises on looking at this problem from a different angle as well. But here what we care about is the the exact solution. What if you uh only care about the precise optimal? And then um we already looked at this last time briefly on the on the theory side. There's a dynamic programming solution and we started with uh with a setup that you can if you fix a certain smaller capacity than your total capacity, you can try to build up a partial solution. And it turns out the way to structurally do that is to restrict the items you're allowed to pick to a a prefix of the items that you have in total.

4:15 Um that's what's shown here in in this animation. You have a DP table that at the end contains this this entry. Zoom in a bit more. Uh in the end contains this entry B N prime B prime in every of the cells. And we can we can fill this table bottom up in the usual way. If you write down the recurrence, that's what we had on the slides. This one that's the same as on the slides. Uh then getting a program that mechanically executes this uh is is easy to produce and it will look like this uh procedure filling this bottom up. You start with the small cases where you have uh either no capacity at all or no items. Um here we put the row with zero items. You can only put value zero and then you try to add one item after the others. So the first initialization says I can with weight zero not get any value.

5:23 obviously done with sorry with no items I cannot get any value and the different columns are the different thresholds how much uh you're willing to put the limit in your in your bucket down but of course if you don't allow any items that all doesn't change then um you're now in let me jump to some intermediate position you're now trying to fill this slot here where you're allowing only the first item A and you can include it or not include it and you're only allowed a capacity of seven weight in total. Now you have two options at this local step to decide about. I can either include this item A or I cannot. I I leave it out and you take the better of the two which in this case because we're starting from empty and a fits in the box at this with this capacity threshold we should include it right that's why we get this value 10 here which comes from the the value 10 of item A and uh nothing else happens in the more general case say we jump to some later point here again um I'm only looking at the prefix of items A, B, and C. And say again, I'm interested in this in this threshold seven.

6:48 The decision I have to make now is should I include this item seven or no? And let me go to the point before. So, we're now looking at this cell for seven. We already know a solution that doesn't include C by definition. and it just looks at the prefix of a and b and it achieves some value there. In this case, it achieves uh this value 40 by picking b. That's the the previous solution. Now I have that's why this b is grayed out. I have a and c that I could still put in. But um all we're doing at this step is deciding about c. So I can either um not include anything then I have the full if I want to include C then I have to make room for C. So the remaining capacity I have here is 7 minus the capacity of C just one. That's why I'm jumping back to column one.

7:49 And then I can take the best solution from all the items that don't include C with just weight one. But the best solution in this case is not pick anything. Nothing fits. The other option I have at this point is I decide not to include C. In which case I have this the full capacity of seven for picking up other items. But I'm uh I'm deciding not to use C. So the best solution in that realm is already known in the in the row above me. I'm looking at the prefix A and B with the same weight. And there the best solution was to include A which had value 40. And so in this case, you see it's uh it's best to stick because this previous solution only gave us 30. Value C is a bit it's a bit stupid. It's rather clunky and big. It doesn't give that much value. So 40 stays as the best solution for this. And that way you can fill the entire table.

8:44 And the other step that's that's standard if you've ever seen any um dynamic programming then you know this last step is also uh systematic. How do you get the optimal solution once you've filled the table? This entry at the bottom right, this tells you, oh, my optimal solution has a solution value of 90. So, I've solved the evaluation problem. Uh but how do I get the solution that led there? Well, by essentially following this backwards, call it a back trace. So, you can check from the 90 again, where could it come from? It could have either either come from above where um I didn't include the item D and then I would have value 70 from using B and C but my value is 90. That's strictly better. So instead I must have used this arc where I get 50 from including this this item D the last one. And then what's left is the part of the knapsack that's not used up by D. So in this case um our uh capacity of seven and then I'm I'm here. I know I've already picked this item D. And now how can I get this value 40 at this point?

10:00 Well uh item C has weight six. So I'm going to jump the entry we've looked at before. I either use this or use this entry to get to 40. And in this case I did not use C. I came from above. And by following your way back to the initial state whenever you pick the uh slanted arc the knot from above then you include this item. Hence the final solution includes B and D where you went the step to the right and the others are not included. Okay, this is undergrads basic stuff. It's the same algorithm that you've used for other problems maybe in some algorithms class. The only thing that's different or new is that we view it from a different angle because we now um want to analyze it with this classes of pseudopolomality on okay that's what we've seen and that's the recurrence again just to have it properly written up on this slide the final answer is is this entry if you just want the solution or you do the back trace to construct the actual witness. How much time did we take to fill this table? That's the dominant part. It has as many entries as we have subpros. And the sub problems range from 0 to n for this n prime and from 0 to b for the b prime. And of course the heavy dimension is this b. As you've seen in the example, it's a much wider table than it's tall. Of course, this is depending on the inputs, but the width could be exponential in the actual input size encoding. Either way, the total number of entries is roughly this product. And you can say each each step took uh one addition and the comparison of two numbers.

11:55 Uh certainly constant number of operations. If you want to do it on a touring machine with these exponentially long numbers, then gets some logarithmic overhead which um that's the time in terms of the values. It's actually linear in the input size if you think about it potentially. So the actual running time here is a bit inconvenient to state. Uh certainly you can say we need roughly that many arithmetic operations and up to polomial factors. uh this is the running time.

12:36 So one way to write this as a formal statement about the running time of a touring machine without building it in detail is to related to this max int. uh we have here the number of subpros.

12:49 This size I that's the uh encoding size which is an upper bound for the number of items. So that's lesser equal n sorry n is n is lesser equal that and max int is certainly an upper bound for our capacity. It's the largest integer in the entire input. Might as well take that to be pessimistic. And the second part is to account for this logarithmic cost model that we need on touring machines. We can only operate on individual bits or individual symbols if you like. So you need a log the size of the number many steps to do the additions.

13:44 I guess I I'm hoping here that there's a clever enough way to do this on a Turing machine without further slowdowns because you also need to find the numbers you read. Let's pretend you can do this always with a linear scan. Either way, um at this point, if you wanted to talk about actual times, running times for implementing this, the Turing machine model loses its relevance. You can clearly do this on a on a word ram in that time even without this maybe. Then you have to say what max how maxin relates to your machine size.

14:20 Either way it's a pseudo polomial algorithm because clearly this can be upper bounded by a polomial in n the size of the encoding and max int. And that was our our definition for pseudo polomial.

14:43 Let's prepare a bit for the future and think about this this uh little question here. As a as a quick reminder, our for the current recurrence build on these items, right? Um the prefix of the items and uh a smaller capacity Hypothetically the the capacities could be uh could be huge but the values are small. How about that?

16:46 still thinking from the from the faces? Maybe. Of course, I can't distinguish what you're thinking about. Can we see the boards? Okay. So uh people are rather skeptical and of course that's correct that NAPSAC is NP hard but like uh we've done it with this with this value version despite the thing being NP hard so it's it's certainly not a strict contradiction but on the other hand there's no guarantee that because it worked one way it should work the other way. Uh now in this case it actually does um so uh the the dynamic program from the slides first. Let me maybe um uh go over that for the for the first um the problem with this is it solves the problem but in the wrong time. If weights and capacities are huge, then this this rough let me uh be let me use this this uh sloppy notation of theta tilda to mean we're lying away small small uh lower order terms in this case these these log of max ins because they just clutter the notation. It's a bit of um uh a bit questionable whether it's always a good idea to do this but here for the sake of the argument we're roughly taking time n * oh let me be you know I can be just I can be precise but uh with slack we certainly need time n * b that was the size of our table and b is the capacity so uh this we say here is is exponential so it's an exponential algorithm. It solves the job but is slow. So that that sadly doesn't work. Um it's true that the problem is hard but that notwithstanding you can do a different DP.

19:09 We somehow have to tilt the table around so that what you what used to be these wide tables with columns for every um value up to B, we now need to make that somehow only depend on the values. That's the only obvious recipe that can work. So, how could that look like? Um, I I'll show you in full, but I think it's it's maybe worth thinking about it for a bit. Um, because in a in a way you can puzzle it out from there. Um, let's keep what worked. So, here we have the prefix of the items.

19:50 So up to this point, I'm allowed to use only the first I items. Now for the for the columns, the only thing that really makes sense is to have somehow the values there.

20:06 Now there's no upper bound for the values per se, but summing up all items values is certainly the best I can possibly get. So say we have some capital V which is the sum of all the values of the items. I certainly don't need to fill the table bigger than that. And then if each of the individual items is at most n² then this is n cubed still polomial. Okay. So what could go into one of these cells?

20:46 I'm restricting to the first I items. Now I can somehow have to make use of the column. That's going to be some value V.

20:54 Let's try to be strict. I want to hit precisely that value. That's one option. Um, and then what goes into the cell is the weight I need to do that.

21:28 And so I could put this as wi prime v prime. See that? That should should do. You can fill this table left to right. It has the slight inconvenience that the last step is to scan the entire row.

21:56 Now, um that seems to be the the most convenient way to state it. you can think about whether the other alternative also works. Um, if you try to achieve at most that value or at least that value, excuse me, it makes the recurrence a bit more annoying. So, uh, let me show this this one as well.

22:29 So the animation which you find on the website has two tabs for capacities and for values and let's again jump somewhere in the middle. So we have our our same input I think is that the yep and suppose again we jump somewhere in the middle.

22:52 So if I if I want to fill this cell, I'm allowed to use just the first two items. But let's make only the decision about B. And I'm trying to reach exactly C6 as the value. Well, uh, looking at the items, tough luck, right? This is not going to work. But how can we systematically rule out that it can't work? I'm trying to reach exactly six. So there's two options. I include A or I don't. If I don't include a then I must reach exactly six with only the prefix one shorter one above. And here sat uh that's not what I wanted. Um here sadly we can't do it with just item A which has value only one. So the it's not the same instance right gets scaled down. Uh is another example same principle. So I can't get to value six with only a. So this is I would need weight infinity and uh so I cannot get this here.

23:56 From the other side if I were to place a b item b I gain four from that. So I still have to gain exactly two from the prefix. Sadly that prefix also doesn't work to two. So my entry here gets an infinity because both of these don't work.

24:20 Now the arrows here with the uh four that would be the weight that we gain. But uh since we started infinity it stays at infinity.

24:34 For a positive example um if you wanted to reach exactly five and you allowed the first three items what's the minimal weight to get there? You can go not including C and get it with weights nine by including A and B. That's what this nine here already compute computed. Or you can include val um C and only reach two with the previous items. Um but sadly that's not possible with A and B. So it stays at this single option from above. Okay. So it almost works the same. I think it's a tad less intuitive for two reasons. First of all, you have to have this exactly the weight idea which u makes the the recursive step here work. Um I think it's also a bit more intuitive to say I'm packing my knapsack piece by piece and so looking at the smaller capacities sounds more natural. But this shouldn't stop you from thinking that sometimes you can transpose the table like this. Um, and it works just the same.

25:50 Okay. Again, in full beauty, it's spelled out in the formulas, but I think this is, as always with these DPS, if you've looked at a an example, it's rather clear how to come up with that formula, and that's how you should do it if you solve a problem. If you just look at that formula, it's very hard to spot if it catches all cases.

26:09 Hopefully, it does. Which means we can now also solve the knapsack problem with a different running time. And in general, the two are I think incomparable. Um we can solve napsac um in this running time. uh um v is the largest the sum of all the weights and then uh I have n * v entries um why do I need another factor n uh because I'm I'm summing up the weights I'm I'm not sure why this extra factor n is needed. I certainly have that many entries to fill for each. I have two options to check. I do an addition and take the minimum.

27:20 Now the weights are big. They're even bigger than max in by a factor n. That's fine. But um within the log that's uh that isn't that much.

27:36 Either way um let's say it's just a conservative upper bound. It's certainly true whether you can try to shape up the n squ or not um is maybe besides the point. So both both of the versions are pseudo polomial in a slightly different parameter. The first one was fine to say it's it's overall pseudo polomial because it already had everything bounded by max int. But here remember max in is at most exponential. So this stays polomial in a more strict sense right it has a more rest more restricted parameter namely this v the sum of the way of the values it's max in cares about all integers and the previous algorithm was fine to show a pseudo polomial in terms of all integers in the input here we can even say I care specifically about these integers and not about the others and it's still pseudo polomial with respect to that the reason why I beat a bit about this is we'll we'll revisit this version of solving the algorithm because it has a nice um a nice connection to approximate solutions that maybe is um at this point is very intuitive to appreciate. So let me maybe show this briefly.

28:56 Uh the main thing that's expensive here is this very wide table which again came from the fact that we wanted a column for every possible value you could potentially attain if you uh only care about approximate solutions. So this is kind of a foreshadow of some very late unit um just because it fits nicely here. I think it makes sense. You can essentially round the columns so that you don't care about precisely 16 versus 17 but just on a coarser scale are you between 15 and 20. Can you do that? >> And you can have a single collapsed column for that and that thereby this is not obvious maybe but you can turn that into a proper approximation algorithm which then shrinks the one thing that here could go exponential the number of columns. And for this you need this by value version. With the capacity version, even if you're willing to compromise on the precision of the value you achieve, say it's okay if you're only half as good as opt or so in terms of the value. This doesn't seem to help because the capacity is a hard constraint. You cannot gain some value by saying I'm just loading my backpack twice as full and hope it'll be fine.

30:16 That's in this in this setup of the problem not allowed. Okay. So keep that essentially as a um as a result where we um worked a bit for the future.

30:38 Now we've illustrated this technique on napsack alone. It turns out the very same trick works for a whole range of problems just because dynamic programming is a very uh general technique that applies to to different problems. Um and you'll look at some in the exercises as well. So in in all of these you're essentially taking the standard approach for doing a dynamic program and just observe that one dimension is basically bounded by max int and so it turns into a pseudolomial algorithm but then on the other side and this is where as always in this module I want to show you both sides we've seen some positive examples where you can do something if the integers are small and then other problems s even though I've not given you much of a chance to play with it yet it just seems hard nobody has found something one example is is traveling salesperson but there's there's other examples where um it feels we cannot find a pseudo polomial time algorithm so um what's missing is the counterpiece how can you give negative evidence that a problem is is hard in the sense that it doesn't have a pseudo polomial algorithm again with the same realm. Uh you'd rather have that connected to some theory as opposed to just your own incapacity, right?