I recently took a test and I had a particularly difficult time with one problem. I would like to know more about this problem: what general class of problems does this problem belong to, what are some good resources to learn more about this class of problems, how should I have recognized the problem for what it was?
So here is the problem, distilled down to its essential components.
You have a task you are trying to accomplish. There are n
different ways to to accomplish that task but each approach has a cost and probability of success associated with it. The problem is to figure out how to order your attempts at the task so that the average cost is minimized.
There is a small twist, if all but your last attempt has failed then you are guaranteed success on your last attempt regardless of the probability of success associated with it.
So here is a concrete example. The following list of tuples represents three ways to complete a task. The first value is the cost and the second value is the probability of success:
[(10,0.5),(8,0.25),(5,0.2)]
One possible order would be [0,1,2]
(each value is the index of an attempt in the above list).
That has an average cost of:
0.5*10 + (1-0.5)*0.25*(10+8) + (1-0.5)(1-0.25)(10+8+5) = 8.975
But the optimal order is [0,2,1]
:
0.5*10 + (1-0.5)*0.2*(10+5) + (1-0.5)(1-0.2)(10+8+5) = 8.8
The obvious way to solve this problem is to simply try every possible order but that has a runtime of O(n!). What you are supposed to know is that by dividing the cost by the probability and sorting the list using that value as the key you will get the optimal order.
I did figure that out eventually but it was not obvious to me at all, I went down a long and winding route and hit many dead ends before I arrived at that solution. So what was the trick here to quickly come to this conclusion?