When we get to a sub-problem we use the recurrence that we developed to compute

the entry in that table using, of course, the entries that we've previously

computed in earlier iterations. So for a given sub-problem where you're

allowed to use the first I items and the residual capacity is X.

What do we know from my thought experiment?

This can only be one of two things. We're just going to do brute force search

through the two possibilities. The two possibilities where we have case

one where we just inherit the optimal solution with one fewer item,

and the same capacity. Or if we're going to actually use item I,

then we compose that with the optimal solution from the first I items.

That leaves enough space for item I. And in that case, we get the value V sub

I for including this Ith item. So this code doesn't quite make sense in

the case where the weight of the current item, wy, is strictly bigger than the,

the capacity, x. that would give us a negative array

index, which, of course, is a no-no. But in that

case, you know, amongst friends we just interpret it as ignoring the second case

of the max. So, you know?

I'm not going to write down the extra code.

But what you would write down is. If WI is strictly bigger than x, then you

just define a of I, x to be equal to a of ai-1, x.

And one crucial point, is that, you know, by the time we need to solve subproblem

with a given I and a given X, we have at our disposal the solutions to all of the

subproblems that we need. In particular, in the previous iteration

of the outer for loop, we computed the solutions to the two relevant subproblems

for evaluating this recurrence. They're there waiting for us available

for constant time lookup. So after this double four loop completes,

sitting there waiting for us in A, in the entry N comma capital W, is the solution

that we wanted. That's the max value solution that can

use any items that it wants and that can use the entire original knapsack capacity

capital W. That's what we want to return.

So that's it. That's the whole dynamic programming

solution for the knapsack problem. Just to make sure this makes sense, in

the next quiz, I want to ask you to analyze the running time of this dynamic

programming algorithm. Alright, so the correct answer is the

second one. And the running time analysis is as

straightforward as it was for the max weight independent set problem.

We just count up the number of sub-problems and look at how much work we

do in each. So how many sub-problems are there?

Where they're indexed by both I and x, there are n plus one choices for I, there

are capital w plus one choices for x. So that gives us theta of n times w

different sub-problems. And all we do for each is a single

comparison amongst previously computed solutions.

So we just do constant work per sub-problem,

giving us the overall running time of n times capital W.

So, a couple other quick notes, which play out in exactly the same way as for

the Maximum Independence Set problem. So I'm not going to discuss the details

here. So first of all, correctness.

Again, it's exactly the same template as in the previous dynamic programming

algorithm, and in our divide and conquer algorithms.

You just go by induction on the problem size.

And, you use the case analysis or a thought experiment to justify, formally,

the inductive step. So this algorithm suffers from a similar

drawback to the max independent set algorithm for path graphs that we looked

at. Namely it computes the value of an

optimal solution not the optimal solution itself.

It returns a number, not an actual subset of items.

But, just like with the independence set problem, you can reconstruct an optimal

solution from the filled in array just by tracing backward.

So the intuition is that you begin with the biggest sub-problem, and you look at

which of the two cases was used to fill in that entry.

If case one was used, you know you should exclude the last item.

If case two was used, you know you should include the last item.

And also, which of those two cases tells you which sub-problem you should trace

back to, to continue the process. So I encourage you to spell out the

details of this reconstruction algorithm in the privacy of your own home.

That'll give you some nice practice with this reconstruction aspect of the dynamic

programming paradigm.