# Find the least combination

Combination / Cost / Probability
1 / 870 /.62
2 / 600 / .65
3 / 540 / .72
4 / 500 / .8
5 / 400 / .82
6 / 320 / .82
7 / 300 / .83
8 / 230 / .86
9 / 200 / .86
10/ 170 / .92

Each item from 1 to 10 is an event with a probability of occurrence associated with it. Probabilities of each item are independent of each other.

Find a subset of these items such that the combined cost (sum of individual costs) is minimized under the constraint that the probability of all the events of this subset occuring (obtained by multiplying their individual probabilities) is less than 0.25.

Please state the subset selected, the probability and the total cost.

Thanks!

-
I think you're going to have to make more of an effort to explain this. In its present form it seems trivially impossible, since all $10$ combinations listed have probabilities greater than $0.25$. The problem may or may not be related to the inconsistency between the plural noun "combinations" and the singular verbs "gives" and "has". –  joriki Nov 26 '12 at 11:08
My guess is that one is meant to choose a subset of $1,2,\dots,10$, compute its cost by addition, and its probability by multiplication. I hope OP will edit a clarification into the body of the question. –  Gerry Myerson Nov 26 '12 at 11:41

To turn this into the classic knapsack problem, recognize that multiplying the probabilities is the same as adding their logarithms. Working with base $2$ logs, you are trying to buy $\log \frac 14 =-2$ in $\log p$. The first item gives you $\log .62 \approx -0.68966$ at a cost of $870$. If you work out the return of the others, you should be able to find which are cheapest.