Dynamic Programming problem (from book “Algorithms”, Dasgupta, problem number 6.23):

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.

+

What ‘s the decomposition equation and time complexity of algorithm?