I am trying to solve this question 8.2 from the book Grokking Algorithms, but I don't agree with the solution the author gave. The question from the book is:

You’re going to Europe, and you have seven days to see everything you can. You assign a point value to each item (how much you want to see it) and estimate how long it takes. How can you maximize the point total (seeing all the things you really want to see) during your stay? Come up with a greedy strategy. Will that give you the optimal solution?

The answer is also provided:

Keep picking the activity with the highest point value that you can still do in the time you have left. Stop when you can't do anything else. No, this wont give you the optimal solution.

Is it better to see the places that take minimum time or max time first? I am not convinced by the author's answer to this question. I can't see how it is best to visit the places which take longer in your schedule...

CodePudding user response：

It seems you missed an aspect in the description of the challenge:

There are two metrics at play, not just one:

• The time needed to visit a place
• The point value a place has

These are independent metrics. The question is to maximize the sum of the second metric, while keeping the sum of the first metric within a given limit (7 days)

The answer suggest to select a next place which has the largest point value among those places whose time still fits within the available time.

This is not saying you should select the place that takes the most time, but the most points (after filtering on available time).

As the book explains, such greedy algorithms do not present the optimal solution, but can in practice come close without having to spend an unacceptable running time on them.