Let's now turn to the analysis of our three step Greedy Heuristic for the Knapsack problem and show why it has a good worst case performance guarantee. So the goal was to prove that the value of the solution output by the three-step greedy algorithm is always at least half the value of an optimal solution, a maximum value solution that respects the knapsack capacity. The key idea behind the analysis is a thought experiment in which we use as a yardstick, an algorithm that gets to cheat. Recall in step one of our greedy heuristic, we short the items in non-increasing order in bang for buck, that is via the ratio of the value over the size. In step two 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 + 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 seven residual units of capacity in the knapsack, and suppose item k + 1 has size ten, then we envision taking 70% of item k + 1 and filling up the knapsack with that fraction. The value, let's say it's prorated, so let's 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, imagine you have a knapsack of capacity three and you had two items, both of size two. Let's say one has value three and one has value two. Well then in the greedy fractional solution you begin by considering item one that has the higher ratio of three halves, that fits fully into the knapsack. Then you move on to item two, it only fits 50% into the knapsack, and the total value of the solution would be the full value of item one, that's 3 plus 50% of the value of item two, so that add one more. So the value of the greedy solution here would be four. The greedy fractional solution would be four. In the next quiz, I'm going to ask you to ponder what properties this greedy fractional solution has relative to feasible of the knapsack instance. The correct answer is D, the greedy fractional is always at least as good as the best nonfractional solution and in fact it can be strictly better. Indeed if you look at the last slide in that simple two 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, cause 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 that is no way that could be better than optimal non fractional solution. 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 an 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 is really what it is. One way you can prove this formally is using an exchange argument, that's what I'll sketch on 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 wait of some of completion times of a bunch of jobs on a single machine. 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 it s. This is a subset of items that fit into the knapsack. So you can imagine for example, a scenario in which the greedy fractional solution packs item number one, and then item number two doesn't fit into the knapsack, but if we take 80% of item number two then that fully fills up the knapsack. So that might be the greedy fractional solution and maybe we're thinking about a non-fraction solution where item one is equally well packed there, but instead of item two, which wouldn't fit, it uses item four which is smaller. And maybe there's some little bit leftover of unfilled knapsack capacity for this non-fractional solution, capital S. So the interesting case is where S packs some stuff that the greedy fractional solution does not and let's suppose it uses up L units of the knapsack capacity via items which are not packed by the greedy fractional solution. Well on the other hand, the greedy fraction solution completely fills up the nap sack. It uses all the space, all capital w units. So if there's L units of stuff in S, which are not in the greedy fractional solution, they'll have to equally be at least L units of stuff in the greedy fractional solution, which are not packed by S. So this might make it seem like the two 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-per-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 capital 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 of S. Since S was arbitrary that shows that the greedy functional solution is in some sense better than optimal. It's better than all the non-fractional feasible solutions. Now it's not clear though why you want to worry bother to do this thought experiment, which transpired in some fantasy world where we were allowed to pack items fractionally. Now what we really care about is our three step greedy algorithm, and that's not in the fantasy world. That's in a real world where we cannot pack items fractionally. So what good could this thought experiment experiment be? Well, as we'll see in the analysis in the next slide, it provides a useful yard stick. A hypothetical bench mark against which we can compare the performance of our three-step greedy algorithm
