So, I'm going to describe the most straightforward

implementation of the dynamic programming algorithm for knapsack.

We're literally just going to explicitly form the 2D

array A.

One index for i will range between 0 and n, the other

index for x will range between 0 and capital W, the original capacity.

There certainly a lot of optimizations you can apply when filling in these tables.

In fact, the future programming assignment will ask you to consider some.

But just to make sure the basic algorithm is totally

clear, let's just stick with that naive implementation for now.

So we begin with the initialization and setting A0X

to be equal to 0 for all x, just

means we take the leftmost column corresponding to i

equals 0 and we fill that in entirely with 0's.

Now in a real implementation there's no reason

to explicitly store these 0's, you know they are

there, but again to keep the picture clear let's

just fill in the 0's in the left column.

Now we proceed to the main while loop and

recall the outer for loop just increments the index i

for the item that we're considering so the outer for loop

is considering each of the columns in turn from left to right.

Now for a fixed value of i for a fixed column, in the

inner for loop we consider all values of x from 0 to capital W.

So that just corresponds in a given column we're

going to fill in the entries from bottom to top.

So we begin this double for loop with the second

column i equal 1 and at the bottom x equals 0.

Now in general when we fill in one of these

table entries, we're going to take the better of two solutions.

Either we just inherit the solution from the column to the left in the same row.

This corresponds to skipping item i.

Or we add the value of the current item.

to the opitimal solution that we extract from

the column one to the left, but also W

[UNKNOWN]

rows down.

So, that corresponds to reducing the residual capacity of W sub i.

Now, for the early subproblems in a column, where

you have essentially 0 residual capacity, it's kind of degenerate.

Right so, if your residual capacity x is

actually less than the weight of the current

item you're considering, w sub i, you have

no choice but to inherit the previous solution.

You're actually not allowed to pack the current item i.

So concretely in this example,

in the first column, notice the weight of the first item is 4.

So that means if x equals 0 or 1 or 2 or 3.

We're actually not permitted to choose item

one, we're going to run out of residual capacity.

So in the first, bottommost four rows

[INAUDIBLE],

we're forced to inherit the solution from the column to the left.

So it is the first four 0's from the left column get copied over to column with i

equals 1.

Now, in this outer iteration of the, in the first outer iteration of

the for-loop, once x reaches 4, now

there's actually an interesting decision to make.

We have the option of inheriting the 0,

immediately to the left.

Or, we can take item 1, therefore getting a value of 3.

And then we inherit the solution from a 0, 0.

And now A000 has a 0, but were obviously happy to get this value of three.

So that's going to determine the max we're going to except V sub i , plus a of 0, 0.

And that gives us a three in this next table entry.