The dynamic programming algorithm is similar to the Knapsack Java code

Question

A critical manufacturing system has n steps that must be performed sequentially; stage i is performed by machine M_i.

Each machine M_i reliably operates with probability r_i and probability 1-r_i of failure (and failures are independent). Therefore, if we implement each stage with one machine, the probability that the whole system works is equal to r_1, r_2, ..., r_n. To improve this probability, we add redundancy by having m_i copies of the machine M_i, which performs step i.

The probability that all m_i copies do not work simultaneously is only (1-r_i) ^ (m_i), so the probability that the stage I completed correctly is 1- (1-r_i) ^ (mi) and the probability that integer (i = 1, n) {1- (1-r_i) ^ (m_i)}.

Each M_i car has a cost of c_i, and there is a total budget B for buying cars. (Suppose that B and c_i are positive integers.) Write the algorithm in java code that sets the probabilities r_1, ..., r_n, costs c_1, ..., c_n and budget B, detects redundancy m_1, ... , m_n, which are within the available budget, and which maximize the likelihood that the system is working correctly (determine the maximum reliability achievable). Also, show how many cars of each type achieve this budget-related reliability.

So, I read in a file that gives me a total budget, followed by the number of cars, and then for each car that I read in cost and reliability. I keep cost and reliability in two linked lists (not sure if this is the best).

try { BufferedReader newFileBuffer = new BufferedReader(new FileReader(inputFile)); budget = Integer.parseInt(newFileBuffer.readLine()); numberOfMachines = Integer.parseInt(newFileBuffer.readLine()); while ((fileLine = newFileBuffer.readLine()) != null) { line = fileLine.split(" "); try { cost.add(Integer.parseInt(line[0])); totalCostOfOneEach += Integer.parseInt(line[0]); reliability.add(Float.parseFloat(line[1])); } catch (NumberFormatException nfe) {}; } newFileBuffer.close(); } catch (Exception e) { e.printStackTrace(); } 

From there, I know that one of each machine should be used once, so I subtract the budget for the total amount that it costs for one of each machine (totalCostOfOneEach), this gives me an extra budget or a redundancy budget if you do this.

 bRedundent = (budget - totalCostOfOneEach); 

Now I'm stuck, I lost what I need to sort through to find a solution. I researched and found this solution , but I do not understand the line

 Pr(b,j)=max{Pr(b-c_j*k, j-1)*(1-(1-r_j)^k} 

So, I know that I created a double array, and I initialize the arrays like this:

 double[][] finalRel = new double[numberOfMachines][bRedundent]; for (int j = 0; j < numberOfMachines; j++) { finalRel[0][j] = 0; } for (int b = 1; b < budget; b++) { finalRel[b][1] = reliability.get(0); } 

Now I'm stuck, I believe that I need to focus on the number of cars, and then on the cost, but this does not work, and I know that I need to somehow include the budget. So here is what I now have that doesn't work at all:

 for (int i = 1; i < numberOfMachines; i++) { for (int c = cost.get(i); c < budget; c++) { finalRel[i][c] = Math.min(finalRel[i-1][c], finalRel[i-1][c - cost.get(numberOfMachines)]*(l)); } } 

I know that the subtask is denoted by finalRel [i, b], the most reliable configuration of machines 1, 2,. ,, I (at least one of each machine) available in budget b. The required response would be finalRel [n, B].

And repetition, if we are on a budget, we return reliability 0 (which means impossibility). If we do not have a budget (b = 0), but we still need to buy cars (i> 0), we return 0 (suppose all ci> 0). If I = 0, we don’t have cars that we have to buy, so the reliability is 1 (if it were 0, then everything would multiply by 0, which is not good). If there is a budget on the left (b> 0) and cars left for sale (i> 0), we try to use all the capabilities of m type I cars for purchase - we need to buy at least m ≥ 1 and up to m ≤ b ≤ gender (b / c_i) ≤ b ≤ B, of which. In each case, the remaining budget will be b - m · c_i. The best reliability for machines 1,. ,, i - 1 will be REL [i - 1, b - m · ci], which must be multiplied by the contribution of m copies of M_i, (1 - (1 - ri) ^ m) or summarized here .

I understand that a lot of information, but I was stuck for a while, so any help is appreciated.

Answer 1

You can work with simpler repetition than this. For i = 0, ..., n and b = 0, ..., B we assume that R(i, b) maximum reliability of the auxiliary pipeline from stage 1 to stage i , taking into account budget B Base cases:

 For b = 0, ..., B, R(0, b) = 1, 

since an empty conveyor never fails and costs nothing. After that, we have a related relapse, which I rewrote a bit for clarity:

 For i = 1, ..., n, For b = 0, ..., B, R(i, b) = max {R(i-1, b - k*c_i) * (1 - (1-r_i)^k) for k = 1, ..., floor(b/c_i)}, 

where k is the number of scenic i cars that we are considering for purchase (definition 0^0 = 1 in case the cars can be absolutely reliable; you have to calculate the power yourself and then reduce the power to multiply, which solves this problem and improves performance). The factor (1 - (1-r_i)^k) is the reliability of stage i with machines k . The coefficient R(i-1, b - k*c_i) is the maximum reliability of the previous stages, taking into account the residual budget. The floor(b/c_i) restriction floor(b/c_i) is the maximum number of stage machines i , which in total cost no more than b .