Sequential prize searching

Question

There are $N$ rooms. In each room $i$, with probability $p_i$ one can find a prize. The cost of searching room $i$ for the prize is $c_i$. A user can search at most $n$ out of $N$ rooms. If a prize is found, he gets a unit reward and stops searching. The problem is to find the sequence of rooms to be searched so as to maximize his expected utility defined as the reward minus the cost.

Mathematically, suppose the user searches rooms $1$ to $n$ sequentially, his overall utility can be written as: $$U=1-(1-p_1)(1-p_2)\cdots(1-p_n)-[p_1c_1+(1-p_1)p_2(c_1+c_2)+\cdots+(1-p_1)\cdots(1-p_{n-2})p_{n-1}(c_1+\cdots+c_{n-1})+(1-p_1)\cdots(1-p_{n-2})(1-p_{n-1})(c_1+\cdots+c_n)].$$

With some algebraic operations and by defining $q_i=1-p_i$, the problem of maximizing $U$ can be mapped to the problem of minimizing the following function $V$: $$V=q_1\cdots q_n+(c_1+q_1c_2+q_1q_2c_3+\cdots+q_1\cdots q_{n-1}c_n).$$

My question is how to solve the combinatorial optimization problem of minimizing $V$? Is there any known problem that can help?

Answer 1

A solution to the problem is an ordered list of $n$ rooms. If $n=N$, Dieter Kadelka's suggestion (searching the rooms in order of decreasing $p_i/c_i$) can be followed and gives an optimal solution computable in linear time. This can be shown by looking at how $V$ changes if two rooms that would be searched consecutively are exchanged.

If $n<N$, an optimal solution can still be found in polynomial time using dynamic programming. By the reasoning above, we can assume that the rooms are ordered by decreasing $p_i/c_i$ and that a subset of them are searched in that order. It remains to find the subset.

Let $U_{max}(r,l)$ be the maximum expected reward obtainable by searching at most $r$ rooms among the (last) $l$ rooms numbered from $N-l+1$ to $N$. For $r>0$, $l>0$, we have $$U_{max}(r,l) = max(p_{N-l+1}-c_{N-l+1}+q_{N-l+1}\cdot U_{max}(r-1,l-1), U_{max}(r,l-1))$$. This enables us to compute $U_{max}$ for $l$ and all possible $r$'s easily if $U_{max}$ is known for $l-1$. We can thus use dynamic programming to compute $U_{max}(r,l)$ for all $0\leq r\leq n$ and $0\leq l\leq N$ in time $O(n\cdot N)$.

An optimal subset of rooms can then be computed in $O(N)$ time from the function $U_{max}$. By a careful computation of the subset of rooms in the same time as $U_{max}$, the algorithm could even be made to run in space $O(N)$.