In this video, we'll develop our second 
dynamic programming solution for the 
knapsack problem. 
Why do we need a second algorithm? Well, 
it's a crucial building block in our 
heuristic that achieves arbitrarily close 
approximation to the knapsack problem in 
polynomial time. 
Recall that in the knapsack problem, the 
input is 2n+1 numbers. 
There's n items, each one has a positive 
value, Vi, and a positive size, Wi. 
Additionally, we're given a knapsack 
capacity, 
capital W. 
Back in the dynamic programming section 
of this course, we already devised an 
algorithm for this problem. 
That algorithm assumed that the item 
sizes were integral and also that the 
knapsack capacity is an integer. 
The running time of that dynamic 
programming algorithm was O(n), the 
number of items, times capital W, the 
knapsack capacity. 
In particular, we get a polynomial time 
algorithm for the special case of 
knapsack when the knapsack capacity is 
not too big, 
when it's polynomial in n. 
It turns out that this is not the right 
special case on which to build an 
algorithm which has arbitrarily good 
approximation in polynomial time. 
Rather, for that kind of heuristic, what 
we really want is a polynomial time 
solution for the special case where item 
values are small, that is precisely the 
solution that we're going to provide in 
this video. 
We will be assuming that the integer 
values are all integers. 
The sizes of the knapsack capacity can be 
whatever and the dynamic program solution 
that we developed will have running time. 
Big O of n^2 times Vmax. 
Vmax here denotes the maximum value of 
any item. 
The running times of the two algorithms 
are more in parallel than the notation 
might suggest. 
Probably, it looks like there's an extra 
factor of n in the second dynamic 
programming algorithm, 
but that's the wrong way to think. 
Think, for the first algorithm, think of 
w as an upper bound on the largest total 
size that a feasible solution might 
possess. 
In the second algorithm, think of n times 
Vmax as an upper bound on the maximum 
total value that any feasible solution 
might possess. 
In the first algorithm, we're focused on 
size, 
in the second algorithm, we're focused on 
value, 
and in any other case, the running time 
is the maximum quantity that we have to 
worry about times the number of items, n. 
Now, since all of you are survivors of my 
dynamic programming boot camp, I don't 
feel the need to develop this solution in 
great detail, let me just jump to the 
relevant subproblems. 
So the subproblems here will be a twist 
on the ones that we used in our first 
dynamic programming algorithm for 
knapsack. 
The part that's going to be exactly the 
same is we're going to have an index i, 
i specifies which prefix of items we're 
permitted to use in a given subproblem. 
Now, in general, in the knapsack problem, 
you're simultaneously trying to get the 
value high while keeping the weight 
small. 
So the way we organized things in our 
first dynamic programming algorithm is 
the second index into a subproblem 
specified the residual capacity x that we 
were allowed to use, 
and then, while respecting that capacity 
x, we asked for the largest value that we 
could obtain just using the first I, 
items. 
Here, we're going to turn that on its 
head. 
We're going to have a second parameter x, 
which is the value that we're striving 
for. So we want to get value x or more 
and we're going to try to minimize the 
total size that we need to use subjects 
to getting the value at least x. 
So the first index, i, arranges as usual 
from 0 to n, 
this corresponds to all the prefixes of 
items you might be interested in. 
The second parameter, x, ranges over all 
of the targets for total value that you 
might be interested in. 
Now, remember, we're assuming in this 
video, that every item value is an 
integer, 
so that means any subset of items will 
have an integral total value so we only 
need to worry about integer values of x. 
In addition, we never need to worry about 
trying to achieve a total value bigger 
than n, the number of items, 
times v max, the largest value of any 
item. 
In fact, you could replace this upward 
value n times Vmax by the sub of the vi's 
if you prefer. 
So if we're given choice of i and x, 
[COUGH] I'm going to use capital S sub 
i,x to denote the optimal value of that 
corresponding subproblem. 
So, that is, the minimum weight, the 
minimum total size that is sufficient to 
achieve a total value of x or more while 
being restricted to using just the first 
i items. 
If there is in fact no way to get the 
target value of x using just the first i 
items, 
that is if the sum of the values of these 
items is already less than x, we just 
define this to be plus infinity. 
So let's write down the natural 
occurrence. 
Let's assume here that i is at least 1. 
So, the structure here is going to be 
exactly the same as it was in our first 
dynamic programming algorithm for the 
knapsack problem. 
Specifically, let's focus on a subproblem 
with a choice of i and a choice of x. 
That final item i is either in this 
optimal solution for the subproblem or 
it's not. 
That gives us two cases and the 
recurrence is just going to do 
brute-force search over the two case, 
because we're trying to minimize the 
total size required to achieve a given 
value target, here, the brute-force 
search is going to take the form of a 
minimum. 
What are the two candidates for an 
optimal solution? Well, the boring one is 
when you don't even bother to use item i, 
then of course, you just inherit an 
optimal solution, a minimum sized 
solution using just the first i-1 items 
achieving the same value target x. 
On the other hand, suppose that in an 
optimal soluton to the subproblem, you do 
actually use item i. 
Well, this contributes to the size of 
item i to the weight of this optimal 
solution. 
So that's going to be w sub i. 
What can we say about the rest of the 
items in this optimal solution? Well, 
because the solution here achieves a 
value target of x, 
the items in this solution other than i, 
must be achieving by themselves a value 
target of x minus v sub i. 
And, of course, by the usual cut and 
paste argument amongst all subsets of the 
first i-1 items with that property, they 
better will have the minimum total 
weight. 
So one quick edge case in this second 
case, if vi is actually bigger than x and 
we have a negative index here, we just 
interpret this quantity as 0, 
that's because item i alone meets the 
value target of x. 
Let's now wrap things up with the 
pseudocode of the new dynamic programming 
algorithm. 
So A will be our usual table. 
It has two dimensions, because 
subproblems are indexed by two 
parameters, i, the prefix that ranges 
from 0 to n, and x, the value target that 
ranges from 0 to, to the maximum 
imaginable value, 
let's say n times Vax. 
So the base case is when i equal 0, that 
is, you're not allowed to use any items. 
In this case, we have to fill it in with 
plus infinity. 
Well, except if x itself is 0, then the 
answer is 0. 
Now, we just populate the table using the 
recurrence in a double for loop. 
The structure here is exactly the same as 
in our first knapsack dynamic programming 
algorithm. 
In the first dynamic programming solution 
that we developed for knapsack, we could 
return the correct answer in constant 
time given the filled-in table. 
That's because of one of the subproblems 
in that dynamic programming algorithm, 
literally was the original problem. 
When i=n and x is equal to the full map 
sack capacity capital W, the 
responsibility of that subproblem was to 
compute the max value solution subject to 
the capacity capital W using all of the 
items, that's literally the original 
problem. 
By contrast, in this dynamic programming 
algorithm, none of the subproblems are 
literally the original problem that we 
wanted to solve. 
In this new dynamic programming 
algorithm, however, none of the 
subproblems correspond directly to the 
original problem that we wanted to solve, 
none of them tell you the maximum value 
of a feasible solution. 
To see why, let's inspect the largest 
batch of subproblems. 
When i is equal to n and you can use 
whatever subset of items that you want. 
The second index of one of these problems 
is a target value x. 
That might be a number, like say 17,231. 
So after you've run this algorithm and 
you've filled in the whole table, what do 
you know in this subproblem? You will 
have computed the smallest total size of 
a bunch, bunch of items that has total 
value at least 17,231. 
So that's going to be some number, maybe 
it's 11,298. 
But, what if your knapsack capacity's 
only 10,000? Then, this is not a feasible 
solution, so it doesn't do you any good. 
Okay, well that's not quite true, it does 
do you some good. 
If you know that every single solution 
that gets value 17,231 or more has size 
bigger than your knapsack capacity, well 
then, you know that the optimal solution 
has to be less than 17,231. 
There is no feasible way to get a total 
value that high. 
Now, you realize that if you knew this 
information for every single target value 
x, and you do once you've filled in the 
entire table, that's sufficient to figure 
out the optimal solution, 
figure out the biggest value of a 
feasible solution. 
All you need to do is scan through this 
final batch of subproblems. 
You begin with the largest conceivable 
target value x, and then you get less and 
less ambitious as you keep finding 
infeasible solutions. 
So you scan from high target values to 
low target values and you're looking for 
the first that is the largest target 
value x, such that there exists a subset 
of items meeting that target value whose 
total size is at most your knapsack 
capacity. 
That is going to be the optimal solution, 
that first target value x, that can be 
physically met given your knapsack is at 
capacity. 
Analyzing the running time is 
straightforward, so how many subproblems 
are there, or equivalently, how many 
iterations of a double for loop do we 
have? Well, it's n outer iterations, then 
n times Vmax inner iterations, so that's 
n^2 Vmax overall. 
Our brute-force searches over only two 
candidates, so we only do constant work 
per iteration of the double for loop. 
In the final line, we do a scan through 
the largest batch of subproblems, so 
that's O of n times Vmax. 
So the running time is dominated just by 
the constant work per subproblem, and so, 
our overall running time is O of n 
squared times Vmax, as promised.