Lets now turn to the analysis about a 3 
step Greedy Heuristic for NAP set problem 
and show why it has a good worst case 
performance guarantee. 
So the goal is to prove that the value of 
the solution output by this 3 step greedy 
algorithm is always at least half the 
value of an optimal solution, a maximum 
value solution that respects the NAP set 
almost at capacity. 
The key idea behind the analysis, is a 
thought experiment, in which we use as a 
yard stick, an algorithm which gets to 
choose. 
Recall that in, [COUGH] step 1 of our 
greedy heuristic, we sort the items in 
non increasing order of bang for buck. 
That is, by the ratio of the value over 
the size. 
In step 2 of the greedy heuristic, we 
pack the items in this order. 
So maybe the first K items, for some 
value of K in this order, fit into the 
knapsack. 
But then we don't have room for item K 
plus 1, and at that point we stop this 
step of the heuristic. 
The thought experiment is to imagine that 
our algorithm gets to cheat and pack a 
fraction of this item k+1 into the 
knapsack to fill it up fully. 
So for example, if we pack in the first k 
items and after that, there's only 7 
residual units of capacity in the 
knapsack. 
And suppose item k+1 has size 10, then we 
envision taking 70% of item k+1, and 
filling it, filling up the knapsack with 
that fraction. 
The value, lets say it's prorated. 
So lets say by, filling in 70% of the 
item into the knapsack, we get 70% of its 
value. 
So we're going to call the output of this 
cheating algorithm the greedy fractional 
solution. 
So just to give a super simple example 
image a knapsack of copacity 3 and you 
had 2 items both of size 2 you'd say 1 
has value 3 and 1 has value 2. 
Well then in the greddy fractional 
solution you begin by considering item 1 
that has the higher ratio we have the 
fits fully in the napsack. 
Then you move on to item 2, it only fits 
50% into the knapsack, and the total 
value of the solution would be the full 
value of item 1, that's 3, plus 50% of 
the value of item 2, so that adds 1, 1 
more. 
So the value of the greedy solution here 
would be, 4. 
The greedy fractional solution, would be 
4. 
[SOUND]. 
In the next quiz I'm going to ask you to 
ponder, what properties, this greedy 
fractional solution has, relative to 
feasible solutions Of the knapsack 
instance. 
The correct answer is D, the greedy 
fractional solution is always at least as 
good, as, the best non fractional 
solution, and in fact, it can be strictly 
better. 
Indeed, if you look at the last slide in 
that simple 2 item example, in that 
instance, the greedy fractional solution 
is Better, strictly better than every 
single feasible solution. 
Now, it's not going to be strictly better 
in every single instance, because there's 
going to be instances where the greedy 
fractional solution happens to use no 
fractions, it happens to just, fill the 
knapsack fully, using 100% of various 
items. 
And then that, there's no way that can be 
better than optimal, non fractional 
solutions. 
So, I'm not going to prove this fact for 
you in gory detail, but let me give you 
just an outline of the argument. 
So the claim, is that the greedy 
fractional solution, of a knapsack 
instance, is guaranteed to be at least as 
good, have at least as large a total 
value, as every feasible solution. 
That is, every non Fractional solution. 
The proof of this would fit in 
fantastically in the greedy algorithms 
section of this course. 
That's really what it is. 
One way you can prove this formally, is 
using an exchange argument. 
That's what I'll sketch at a high level 
here. 
I'll leave it as an exercise to you to 
fill in the details, but it's really very 
similar to our proof of optimality for 
the greedy algorithm, for why, sorting by 
ratios minimizes the weighted sum of 
completion times, of a bunch of jobs on a 
single. 
[INAUDIBLE] So how should we proceed,we 
have to prove that the greedy fractional 
solution is as good as every feasible 
solution, every non-fractional solution. 
So fix such a solution, call is S. 
This is a subset of items that Fit into 
the knapsack. 
So you could imagine, for example, a 
scenario in which the greedy fractional 
packs item number 1. 
And then, item number 2 doesn't fit, into 
the knapsack. 
But if we take 80% of item number 2, then 
that fully fills up the knapsack, so that 
might be the greedy fractional solution, 
and maybe we're thinking about non 
fractional solution where Item 1 is 
equally well packed there, but instead of 
item 2 which wouldn't fit, it uses item 4 
which is small and then may be there is 
some little bit left over of unfilled 
[INAUDIBLE] capacity for this 
non-fractional solution S. 
So, the interesting case is where S 
packed some stuff that the greedy 
fractional solution does not, lets 
suppose it uses it uses l units of 
[INAUDIBLE] capacity via items which are 
not packed by the greedy fractional 
solution. 
Well, on the other hand, the greedy 
fractional solution completely fills up 
the knapsack. 
It uses all of the space, all W units. 
So, if there's l units of stuff in s, 
which are not in the greedy fractional 
solution, there have to equally well be 
at least, l units of stuff in the greedy 
fractional solution, which are not packed 
by it. 
S. 
So this might make it seem like the 2 
solutions are apples and oranges. 
Each of them packs some stuff that the 
other one doesn't. 
But they're not apples and oranges, the 
greedy fractional solution really is 
better. 
Why? Well, by the greedy criterion 
everything not packed by the greedy 
fractional solution, has ratio, has bang 
for buck Worse, than everything that it 
did pack. 
So these l units that are missing from 
the greedy fractional solution, are less 
valuable than the l units that it 
includes. 
So, since the l units of stuff in the 
greedy fractional solution, missing from 
S, are a better use of space, than the l 
units of stuff that are in s, but not the 
greedy fractional solution. 
Some, easy algebra shows that indeed, the 
overall value of the greedy fractional 
solution, is at least the overall value. 
Value of S. 
Since S was arbitrary, that shows that 
the greedy fractional solution is in some 
sense better than optimal, its better 
than all of the non-fractional feasible 
solutions. 
Now its not clear that women [INAUDIBLE] 
bothered to do this thought experiment 
which transpired in some fantasy world 
where we're allowed to pack items 
fractionally. 
Now what we really care about is the 3 
step greedy algorithm and that is not in 
the fantasy world, that's in the real 
world where we cannot pack items 
fractionally. 
So, what good could this thought 
experiment [INAUDIBLE] be. 
Well, as we'll see in the analysis in the 
next slide, it provides a useful 
yardstick, a hypothetical benchmark 
against which we can compare the 
performance of our 3 step greedy 
algorithm.