You play a game as follows. You have $N$ coins in front of you. For each coin you know:
- the probability to get "heads" $p_i$
- the prize $r_i$ you get when you get "heads" (as money)
The rules are:
- choose a coin
- if you get heads, you're done, you get the prize and the game stops.
- otherwise you can choose and flip another coin (you can't flip twice the same coin).
- and so on until you get heads or you reach a limit of $K$ flips ($K\leq N)$.
You want to find the best strategy: the one with highest expected payoff. Some simple cases:
- For $K=N$ the solution is just ordering by decreasing $r_i$ ($p_i$ does not matter).
- For $K=1$ the solution is just choosing the coin with highest expected payoff $p_ir_i$.
For $1<K<N$, it doesn't seem to be that simple. One solution is brute force: compute expected payoff for all partial permutations.
Do you see an (algorithmically) better solution?