Video 3-2: Knapsack

0:02 In the next section we'll look at the knapsack problem again and see a concrete example for what these pseudo polynomial algorithms can look like. Of course any actual polynomial time algorithm is also pseudo polynomial if you want, but um an example where pseudo polynomial does something interesting.

0:23 I skipped the definition earlier because uh um it's coming here in more detail anyways. The knapsack problem is the following. You're you're given n objects and these each have um a weight and a value. You also have some some uh threshold or some some capacity. It's not just a It's not a threshold in the optimization sense. This is the optimization problem. Um this B is a capacity for some container and you want to take as many objects as you can fit in your container. But what you really care about is the total value. So it's it's weighted in all all sense. So um the optimization problem asks for picking a subset of these items so that the uh weights sum up to at most B but you maximize this total value that you get from these items. And you can say this is the burglar problem. You have items of different value and weights and you want to still run fast enough or maybe you can make a more positive less criminal analogy.

1:33 That's the knapsack problem. Now it is NP-hard. We've not shown that. Um I wonder if this is This was somewhere in the exercises. You might have kicked it out. Maybe you've also seen a solution. If you think about it, this this is a problem where it's not so obvious why it would maybe have a reduction from 3-SAT or something of this sort. Because it only talks about these numbers.

1:57 Also from what I'm telling you now, I mean, you know the context it arises in, there should be probably some pseudo polynomial algorithm, otherwise I wouldn't show this example now. So, any reduction will have to produce long numbers. Because for small numbers, we can actually solve this fast. Okay. Uh let's not do the reduction. Um let me instead uh try to show you the solution. And maybe this is a flashback for some of you. Uh I tried to give a very structured uh or recipe for designing dynamic programming algorithms and efficient algorithms. Uh if you've not seen this before, maybe it doesn't help you now too much, and we'd rather just do the example. The main The main point is if I can somehow come up with a recursive description of the cost of a problem, then oftentimes I have uh a structured way to get to the actual algorithm. And that's what's what's spelled out here, that the these latter half of the steps are essentially following the recipe.

3:10 We'll maybe come back to this a bit um next time. I want to briefly teaser the solution so that you can think about that. Um for our knapsack problem, uh um you can you can try to uh spell out the options um that you have to pick certain elements, but there's an exponential number of different sizes uh different number of sets of elements. So, if you had a subproblem for each possible subset, that's never going to be polynomial time. So, you have to be slightly more clever. And the idea here is restrict the sub problems by only allowing a prefix of the elements. You don't fix which ones you pick, but you only allow the first n prime of the objects so far. And you restrict the the capacity of the knapsack further. So, the idea is that you pack some of the prefix elements into a smaller knapsack and leave space for maybe the next ones.

4:16 Then you guess um for the next item whether or not you include it. There's only two options. And for that you can set up a recurrence for the best value you get. So, often times the crucial thing in a dynamic program is to find what is the thing you put in the table. And here we write down the value of the best possible solution when I'm only allowed to pick the first n prime items and I'm only allowed to fill capacity b prime.

4:48 From this you already see how many sub problems do I have? Well, the first component is from 1 to n. I need all of these, so that's n. And for the second, I don't need capacities larger than the thing I'm eventually allowed, but I might need all the smaller values. So, it's n times b. Now, n is relatively small because I have these n items each of which I write down some numbers. So, um my input certainly will be at least n bits long. Actually, a bit more even uh necessarily. But for b, that's not the case. B is a number. B is only bounded by max int. And so, I'm I'm here in a way uh linear in both separately or polynomial in their product, uh but one is bounded only by max in, not by the encoding size.

6:09 And as as you remember, in principle, B could be exponential in in the input size. >> [snorts] >> Okay, let's let's continue next time how to puzzle the rest together. This is, in a way, with this definition set, the rest is undergrad algorithms, applications of dynamic programming. What follows, how to solve this, doesn't really depend on pseudo polynomiality. The pseudo polynomial part only comes in that we're using a table whose size is, in general, exponential, but has a dependency on this largest integer that makes it polynomial in the number of max in, this polynomial. And that's kind of it. That is also what most pseudo polynomial algorithms do.

6:53 There's a few other interesting exceptions, they're a bit more esoteric. But oftentimes, it comes down to a dynamic program where one of the dimensions is bounded by max in, not by the encoding length.