Explore
For Enterprise
Join for Free
Log In

Arts and Humanities
Business
Computer Science
Data Science
Information Technology
Health
Math and Logic
Personal Development
Physical Science and Engineering
Social Sciences
Language Learning
Degrees
Certificates

Explore all of Coursera

Browse
Search
For Enterprise
Log In
Join for Free

Analysis of a Greedy Knapsack Heuristic I

Loading...

Shortest Paths Revisited, NP-Complete Problems and What To Do About Them

Stanford University

4.8 (470 ratings) | 19K Students Enrolled

Course 4 of 4 in the Algorithms Specialization

The primary topics in this part of the specialization are: shortest paths (Bellman-Ford, Floyd-Warshall, Johnson), NP-completeness and what it means for the algorithm designer, and strategies for coping with computationally intractable problems (analysis of heuristics, local search).

Skills You'll Learn

Data Structure, Algorithms, Np-Completeness, Dynamic Programming

Reviews

4.8 (470 ratings)

5 stars
403 ratings
4 stars
59 ratings
3 stars
5 ratings
2 stars
2 ratings
1 star
1 ratings

JF

Jan 14, 2018

I love Tim's excitement for algorithms. He really stands out as a quality teacher in his selection of content, explanations and enthusiasm.

LL

May 02, 2018

Fantastic course by a fantastic Teacher, Prof. Roughgarden manages to turn the dry subject of Algorithms into a hot sexy one!!

From the lesson

Week 3

Approximation algorithms for NP-complete problems.

A Greedy Knapsack Heuristic14:01

Analysis of a Greedy Knapsack Heuristic I7:12

Analysis of a Greedy Knapsack Heuristic II9:42

A Dynamic Programming Heuristic for Knapsack11:37

Knapsack via Dynamic Programming, Revisited10:25

Ananysis of Dynamic Programming Heuristic15:12

Taught By

Tim Roughgarden
Professor

Transcript

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

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play

Coursera
About
Leadership
Careers
Catalog
Certificates
MasterTrack™ Certificates
Degrees
For Enterprise
For Government

Community
Learners
Partners
Developers
Beta Testers
Translators

Connect
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Tech Blog

More
Terms
Privacy
Help
Accessibility
Press
Contact
Directory
Affiliates