There's a problem whose solution startles me because at first sigh, I wouldn't imagine that it could be solved so easily. The problem is:
There are n tasks, each task
t_i has a weight
w_i and a length
l_i. Find an order of tasks
t_n that minimizes the total cost of completion, where the cost of completion of each task is
c_j * w_j, where
c_j is the time it has passed since you started working on the first task until you finished the jth task.
If we analyze the problem a bit, we can see that the task that we choose to complete first will impact the cost of all the remaining tasks. For example, say you only have 2 tasks:
w_1 = 1 and
l_1 = 5 and
w_2 = 4 and
l_2 = 2
If we started first
task_1, its cost would be
5 * 1 = 5 while if we started first
task_2, its cost would be
2 * 4 = 8. But, the cost of completing
(5+2) * 4 = 28. This shows clearly that the order of completion of one task affects the cost of completion of all the remaining tasks.
Considering how each task we decide to complete next impacts the cost of all the remaining tasks, it startles me that the best order is simply the order we get by sorting the tasks by their ratio
Which part of the problem hints that the solution doesn't require to check all the possible orders?
The problem is taken from Algorithms Illuminated 3 by Tim Roughgarden.