0
$\begingroup$

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!

  • 0
    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.2012-11-26

1 Answers 1

1

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.