I have a row of $n$ upside down cups in front of me. There may be balls under some of these cups, and my task is to lift the cups one at a time (in some order, to be determined as below) until I find a ball or have lifted all the cups.
For each $k \in \{1, 2, ..., n\}$, cup $k$ covers a single ball with probability $p_k$, and otherwise no ball. The probabilities $p_k$ are independent and may take any value on $[0,1]$.
There is also a cost $c_k \geq 0$ to lifting cup $k$ to see whether there is a ball under it. Thus, if we let $s$ denote the permutation of $\{1, 2, ..., n\}$ that gives the order in which I lift the cups, then the expected total cost that I rack up en route to uncovering a first ball is $$f(s) = \sum_{k=1}^n c_{s(k)} \prod_{m=1}^{k-1} (1-p_{s(m)})$$ (where $\prod_{m=1}^0 (1-p_{s(m)}) = 1$).
I would like to minimize this expected total cost, which translates to minimizing $f(s)$ over all possible permutations $\{s\}$. Is there an algorithm for doing this that is more efficient than simply computing $f(s)$ for all $n!$ permutations of the cups?
First, let's simplify the notation a bit by setting $q_k = 1 - p_k$. And again by assuming for the time being that you've decided on a permutation and have simply renumbered your cups accordingly. So you are turning over the cups in order $1, 2, 3, ...$.
The cost of looking under $N$ cups is $$\begin{align}C_1 &= \sum_{k=1}^N c_k \prod_{m=1}^{k-1} q_m\\&= \sum_{k\ne M, M+1} c_k \prod_{m=1}^{k-1} q_m + (c_{M} + q_Mc_{M+1})\prod_{m=1}^{M-1}q_m\end{align}$$ If you exchange the order of cups $M, M+1$, you get $$C_2 = \sum_{k\ne M, M+1} c_k \prod_{m=1}^{k-1} q_m + (c_{M+1} + q_{M+1}c_M)\prod_{m=1}^{M-1}q_m$$ And the difference is $$\begin{align}\Delta C &\propto (1-q_M)c_{M+1} - (1 - q_{M+1})c_M\\&\propto p_Mc_{M+1} - p_{M+1}c_M\\&\propto \frac{c_{M+1}}{p_{M+1}} - \frac{c_{M}}{p_{M}} \end{align}$$
Thus change in cost from swapping two adjacent cups in the order is negative if $$\frac{c_{M+1}}{p_{M+1}} < \frac{c_{M}}{p_{M}}$$
It follows that the lowest cost occurs when $\displaystyle \frac{c_k}{p_k}$ increases with $k$. All other orderings can have their cost reduced by exchanging two adjacent cups somewhere.