[MUSIC] So far we have solved the Knapsack problem for a special, special, special case. It doesn't seem very interesting, but we get to use the same ideas to try to solve a slightly more general case. What will be this less special, special case? The case when the item values are small integers. So every item, as before, has a size and a value, but the size is no longer equal to the value. Their size can be arbitrary, but the item values are small integers in the range one through N where N is could be fixed. How are we going to solve this? Well, we will extend previous ideas from the special, special case. How did we solve the special, special case? We used dynamic programming. So let's start again with dynamic programming. The idea of dynamic programming, we have to figure out what interface to define given a partial solution for the first i items. We want to remember enough of the partial solution so that we're able to complete the solution optimally. So what will we do? We'll add some stuff to this spot. We'll complete things optimally here for an arbitrary beginning. So we need an interface that tells us what to remember here. What to remember. Before, we remembered for every i, for the first i items, whether there was a subset that could achieve a certain value v for every possible value v. Now again we're interested in the first i items and we are interested in a particular value v. But in order to figure out whether we can add some stuff on top of a solution, what are we going to do? We're going to add some stuff, add some stuff here, and for this we need to remember the size. So, we must remember the size. How are we going to remember the size? The size can be arbitrary, can be small, can be large, can be long numbers, difficult things. The sums there are many, an exponential number of possibilities. So what we'll do is, we'll remember the interesting sizes inside the table entries. Inside A[i,v] we'll remember the size. Let's be more specific, in A[i,v], we will remember the size is achievable for subsets of our first i items of value v. Really? Not quite. For any subset of our first items of value v, there could be many different sizes achievable. All we need to remember is the minimum, the minimum of these values. Why? Because if for the same value we can achieve it with this size, this size, this size inside our Knapsack, then we might as well use the minimum possible size. So in A[i,v] we define this entry of a table as the minimum size achievable by any subset of the first items whose total value equals v. And now that we have the definition of our GP table, we need to figure out a recurrence so that we'll be able to fill these entries in the algorithm. When? When there is some subset of the first i items some to size s while having total value equal to v. Well it depends, it depends on item i. It depends on whether item i is in the subset or not. Depends on whether the subset contains item i. Two cases, two cases. Case one, item i is not in the subset. Then it's easy, we just have to look at the first i- 1 items. And then we have to be able to reach 5f with total value v. Case two, item i is in the subset. Then it's easy, it uses size si of the Knapsack. So the other items of the subset must sum to size s- si. And it gives us value vi. So the rest of our subset must give us value v- vi. So this now gives us, this reasoning now gives us a recurrence formula. Can be expressed algebraically as follows. Let A[i,v] Denote the minimum size achievable by any subset of our first i items of total value v. If v is greater than or equal to vi, then A[i,v] is the minimum of two possibilities. The one when i Item i is in the subset, and a one when it's not. The minimum of two possibilities, the first possibility is A[i- 1,v]. The second one is A[i- 1,v- vi]. That's the total size minimum achievable by a subset of first i minus some items that sum with total value (v-vi)+si. The size of item i. What about the else? Else, else, else. If v is strictly less than vi, then what? Then item i cannot go in a subset and then A[i,v], clearly is just A[i-1,v]. Simple. So this gives us a recurrence. We will use it to fill the table entries by order of increasing the value of i, and that leads us to our algorithm for this special case. Here's the algorithm. I did not detail the initialization. I did not detail the last part. But this is easy. You can check it yourselves, by yourselves that this works. What's important is the line with the recurrence, the line with the min, this line. And what is the run time, run time? Line one, O of nN. Line two, constant. Line three, a for loop with time big O of n. This for loop includes some other loops, two loops that together have v scanned from 0 to nN. Why nN? Because this is the maximum value conceivable. Why? Because every item has value at most N. Even if every item is put in the Knapsack, the total value will be nN, little n times capital N. And so, because of these two for loops, the runtime will be o(n^2N), when capital N is a constant, this is quadratic. So, if we look at the main idea of this algorithm, how did we design this algorithm? We have to think of trying the method of dynamic programming, and the main idea really came up in the definition of the DP array. A definition that was chosen in just the right way so that we would have a recurrence formula. We look at this, we see that it works in polynomial time. It gives us the optimal way to put items in our Knapsack so as to maximize the value while respecting the capacity. So at this point what have we done? We have solved the Knapsack problem exactly in the case where all the items had small value. In the next part, what we will do is build on this to design an approximation algorithm finally for Knapsack.