Question

PS8: When using comparators, they return True/False for only the single and cannot handle equivalent cases (two courses of work 1, with different values, e.g. which is called out in the assignment). Easy to fix by changing it to a '<=' in the cmp and adding to the algorithm, but is that appropriate behavior? I could see the argument that the algorithm should choose the first to evaluate true, which may not be 'optimal'.

Answer 1

that might be the point of the exercise - to see how they act differently;

Answer 2

I'm not sure I follow when you say "how they act differently". I mean, the behavior is straightforward- I'll add (trivial) computational complexity if I allow the comparators to pass equivalencies then do additional checking in the greedyAlgorithm itself, whereas if I leave the comparators as is and take their output verbatim, I'll run (trivially) faster and have the knowledge that for certain dictionary/maxWork combinations, I won't find the optimal solution.

However, that non-optimal solution doesn't seem to be related to the non-optimization due to using a greedy algorithm, which I thought had more to do with the fact that I'm not looking at all possible outcomes. That is, in my greedy algorithm, I always take the next best option, but because of how the definition of 'best' was presented to us, even though the cmp says it is 'best', it isn't necessarily.

Answer 3

I'm a little confused about the greedy strategy for ps8 prob 2. I thought greedy was to take the the most valuable items first until max work was reached. that means either looping thru the dict (mult times) or converting the dict to a list and sorting the list. Is this the strategy you are taking with this problem?

Answer 4

@ skibum you are correct.

a list sort would be a cool solution, you could use the three different comparator functions for either the cmp or key arguments