A mission-critical production system has n stages that have to be performed sequentially; stage i is performed by machine Mi.
Each machine Mi has a probability ri of functioning reliably and a probability (1 - ri) of failing (and the failures are independent). Therefore, if we implement each stage with the single machine, the probability that the whole system works is r1 × r2 × · · · × rn. To improve this probability we add redundancy, by having mi copies of the machine Mi so that stage i can be performed by mi independent copies. Each machine has a nonnegative cost ci
, and there is a total budget B to buy machines.
Given the probabilities r1, · · · , rn, the costs c1, · · · , cn, and the budget B, ?nd the redundancies m1, · · · , mn
that are within the available budget and that maximize the probability that the system works correctly. Devise
an ef?cient algorithm.
You can assume the costs ci and the budget B are integers.