I have just started to learn Dynamic Programming, and so far I have studied the few basic concepts; longest common subsequent problem, edit distance problem and the knapsack problem. I have attempted to solve the following exercise that is related with this topic, and so far I think I have a way how to approach it , but I am stuck at one point. Please, if you can, read my solution and tell me whether I am doing something wrong. I absolutely do not want you to solve it for me, just give me some help/hints.
A mission-critical production system has n stages that have to be performed sequentially; stage i is performed by machine M_i. Each machine M_i has a probability r_i of functioning reliably and a probability 1-r_i of failing (and the failures are independent). Therefore, if we implement each stage with a single machine, the probability that the whole system works is r_1,r_2,...,r_n. To improve this probability we add redundancy, by having m_i copies of the machine M_i that performs stage i. The probability that all m_i copies fail simultaneously is only (1-r_i)^(m_i), so the probability that stage i is completed correctly is 1-(1-r_i)^(mi) and the probability that the whole system works is prod(i=1,n){1-(1-r_i)^(m_i)}. Each machine M_i has a cost c_i, and there is a total budget B to buy machines. (Assume that B and c_i are positive integers.) Given the probabilities r_1,...,r_n, the costs c_1,...,c_n, and the budget B, find the redundancies m_1,...,m_n that are within the available budget and that maximize the probability that the system works correctly .
________________________ MY PROPOSED SOLUTION
- We need to make sure that all the given probabilities are different from 0, meaning for all r_1 !=0 (if we had a probability 0 the system would not work)
- We must make sure that we have at least one machine of each type, meaning we have one copy of each machine (if we do not have a certain machine, like in point 1 the system would not work). In addition, by having already a copy of machines from m_1,...,m_n, the total cost of this machines would be sum(i=1,n)=c_i. This means that from the total budget B we need to subtract this cost, and get the extra budget for the redundant machines. B_extra= B-sum(i=1,n)=c_i
To find the redundant number of machines we just need to model the problem as knapsack. Subproblem: K(c) ->maximum probability that a system works correctly. Recursive relationship:
for c=1 to B_extra K(c) = max{K(c-c_i)*(1-(1-r_i)^(m_i)):c_i<=c}
Now, the points where I am stuck and need help are:
- The way I am defining the problem, is it correct or am I missing any special case? I think that the recursive relationship should work fine; any reason why it shouldn't?
- How should I keep track of the number of m_i machines. I know that the initial value for each m_i is one (from point 2 we need at least one copy of each machine). Should I just keep track of another variable in the problem K(c, m) and every time increase m_i++?