Question

I'm stuck on problem 2 of problem set 8. I can't figure out if I am misunderstanding something or if there is a mistake in the problem set:

Answer 1

Straight of the problem set:

For instance, if we’re given the following subject dictionary, smallCatalog, and a maximum of 15 hours of work:
# name value work
{'6.00': (16, 8),
'1.00': (7, 7),
'6.01': (5, 3),
'15.01': (9, 6)}
If we were to use greedyAdvisor with the value comparator (look below to see what the function’s arguments are):
>>> greedyAdvisor(smallCatalog, 15, cmpValue)
your function will use the comparator and select 6.00 first, then 15.01, and return the following dictionary:
{'6.00': (16, 8), '15.01': (9, 6)}
The other subjects are not included because they would bring the total workload above the maxWork limit.

Answer 2

Why wouldn't it 1.00 or 6.01 first before 15.01? They would not push the max past 15 if they are added before 15.01? Or am I misunderstanding what a greedy algorithm is supposed to do? From what I gathered the algorithm is supposed to simply grab the first solution that fits the criteria and then abandon all other possible solutions. I hope someone has the time to explain this to me!

Answer 3

**why woudn't it select 1.00 or 6.01

Answer 4

Because it selects a subject with maximum *value*, not with maximum *name*. If you look at your example the value of subject "6.00" is the highest, followed by the value of "15.01".

The idea behind a greedy algorithm is to take the highest-valued solution available at each step (note that the metric used to determine the value will vary from problem to problem).

Answer 5

where is problem set

Answer 6

my understanding of greedy is - you run through the list/dictionary and pick the item with the highest value that doesn't exceed the work constraint - then you run thru it again and pick the item with the highest value that doesn't exceed the 'new' work constraint - keep doing it till you can't pick anything because you ran out of work

each time you run thru the dictionary/list you choose a 'locally' optimal solution - greedy doesn't necessarily produce a 'globally' optimal solution