# Dynamic programming: Knapsack with repetition, Find the number of redundant machines

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

1. 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)
2. 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
3. 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:

1. 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?
2. 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++?
-

## migrated from stackoverflow.comNov 14 '12 at 12:32

This question came from our site for professional and enthusiast programmers.

the maximum sucesss probability would be the minimum failed probability, and each machine should be at least 1, so we can reduce the original package B into B'= B-sum(c_i), and each machine's dp[i][0] should be initialized as fail probability (1 - r_i).

so, we can find the dp state transition based on the modified knapsack(size is B') problem as above:

dp[i][c]    = min(dp[i-1][c], dp[i-1][c-cost[n]]*(1-r_i))
0<= c <=B' , 1<=i<=n, B' = B-sum(c_i)


intitial of the dp array would be like this:

dp[0][0~B'] = 1
dp[i][0]    = 1-r_i, 1<=i<=n


so the pseudocode would be like :

 for(int i = 1 ; i<=n;++i)
for(int c = cost[i] ; c<=B';++c)
dp[i][c] = min(dp[i-1][c], dp[i-1][c-cost[n]]*(1-r_i)))

-

R(b,j): the max reliability for constructing the system with stage 1....j with budget b

 for j=1 to n
Pr(0,j)=0
for b=1 to B
Pr(b,1)=r_1

for b=1 to B
for j=1 to n
for k=1 to b/c_j
Pr(b,j)=max{Pr(b-c_j*k, j-1)*(1-(1-r_j)^k}
Red[B][j]=k
print(Red[ ][ ])

-