Question

How's my "greedyAdvisor" (problem set 8-2)?

So first of all, I didn't really understand how to use the comparator (comparing two values) in order to find the best option. So I just bypassed that altogether, and instead used an approach similar to "max": Iterate through the list and the "best" according to one of three rubrics - given the constraint that the work of that course <= maxWork. Then, remove that course from the dictionary, run again on the remaining values, and repeat until there's no more to add.

Answer 1

Here's the code of this implementation, for just the "work" comparison. There are two more corresponding sections for the "value" and "ratio" comparisons.

http://pastebin.com/b76egEyT

And since it's long and convoluted (especially if you include all three), here's the pseudocode:

1) Scan dictionary for the subject that best satisfies what you're looking for (i.e. least work, highest value or best work/value ratio) AND doesn't exceed your maximum work.
2) Remove that value from the dictionary and search with the remaining items until you return no further results.
3) Return what you've found.

Now, the program SEEMS to work OK; it gives me nice results and it doesn't take long. But its implementation is different from the instructions, and it's also different from a solution that I looked up online (and gives different results too - though not necessarily any less correct). What I wonder is, (a) is something about this answer incorrect, in terms of the outputs it gives? and (b) by not doing the program according to their instructions, will I set myself up for hopeless confusion on the remaining problems?

Answer 2

yep that's what greedy dose - take the best (however best is defined) then take the next best ... with no attempt at optimizing.

the comparators are different ways to define best - they are trying to get you to understand that you can write a kind of generic algorithm that you can pass functions to as well as data - there could be some utility in doing that. in this case you can write one function to find the best and then by passing it different definitions of best (the comparator functions) you can see if one definition of best is better than another - sometimes it is not easy to tell in advance what the best definition is.

Answer 3

here is mine http://dpaste.com/709733/:

b) i don't think it will matter

a) hard to say without running it - you didn't include deldict in your paste