Dynamischer Programmieralgorithmus ähnlich Knapsack Java Code

Question

Ein unternehmenskritisches Produktionssystem hat n Stufen, die nacheinander ausgeführt werden müssen; Stufe I wird von der Maschine M_i ausgeführt.

Jede Maschine M_i hat eine Wahrscheinlichkeit r_i, die zuverlässig funktioniert, und eine Wahrscheinlichkeit 1-r_i des Fehlers (und die Fehler sind unabhängig). Wenn wir also jede Stufe mit einer einzigen Maschine implementieren, ist die Wahrscheinlichkeit, dass das ganze System funktioniert, r_1, r_2, ..., r_n. Um diese Wahrscheinlichkeit zu verbessern, fügen wir Redundanz hinzu, indem wir m_i Kopien der Maschine M_i haben, die die Stufe i ausführt.

Die Wahrscheinlichkeit, dass alle m_i Kopien gleichzeitig versagen, ist nur (1-r_i)^(m_i), also ist die Wahrscheinlichkeit, dass Stufe i korrekt ausgeführt wird, 1- (1-r_i)^(mi) und die Wahrscheinlichkeit, dass das ganze System funktioniert prod (i = 1, n) {1- (1-r_i)^(m_i)}.

Jede Maschine M_i hat eine Kosten c_i, und es gibt ein Gesamtbudget B, um Maschinen zu kaufen. (Angenommen, B und c_i sind positive ganze Zahlen.) Schreiben Sie den Algorithmus in Java-Code, dass die gegebenen Wahrscheinlichkeiten r_1, ..., r_n, die Kosten c_1, ..., c_n und das Budget B die Redundanzen m_1, .. finden. ., m_n, die innerhalb des verfügbaren Budgets liegen und die Wahrscheinlichkeit maximieren, dass das System korrekt arbeitet (die maximal erreichbare Zuverlässigkeit bestimmen). Zeigen Sie auch, wie viele Maschinen jedes Typs diese innerhalb des Budgets gebundene Zuverlässigkeit erreichen.

Also lese ich in einer Datei, die mir das Gesamtbudget erlaubt, gefolgt von der Anzahl der Maschinen, und dann für jede Maschine lese ich die Kosten und die Zuverlässigkeit. Ich speichere die Kosten und die Zuverlässigkeit in zwei verknüpfte Listen (nicht sicher, ob dies am besten ist).

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(); 
     } 

Von dort Ich weiß, dass man von jeder Maschine einmal verwendet werden müssen, damit ich das Budget durch die Gesamtmenge für eine von jeder Maschine (totalCostOfOneEach) kosten subtrahieren, das gibt mir Budget übrig oder die Redundanz Budget wenn du möchtest.

Jetzt ist, wo ich feststecke, ich bin verloren auf, was zu Schleife, um die Lösung zu finden. Ich habe recherchiert und fanden diese solution aber ich verstehe nicht, die Linie

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

Also, was ich weiß ist, ich ein Doppel Array erstellt haben, und ich initialisieren die Arrays als so:

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); 
} 

Jetzt ist Wo ich feststecke, glaube ich, dass ich die Nummer der Maschine und dann die Kosten wiederholen sollte, aber das funktioniert nicht und ich weiß, dass ich das Budget irgendwie integrieren muss. Also das ist, was ich zur Zeit, dass überhaupt nicht arbeiten:

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)); 
    } 
} 

Ich weiß, dass das Teilproblem bezeichnet finalRel [i, b], die zuverlässigste Konfiguration von Maschinen 1, 2,. . . , i (mindestens eine von jeder Maschine) innerhalb des Budgets verfügbar b. Die gewünschte Antwort ist finalRel [n, B].

Und die Wiederholung, wenn wir unter Budget sind, geben wir die Zuverlässigkeit 0 zurück (was nicht möglich ist). Wenn wir das Budget überschreiten (b = 0), aber immer noch Maschinen kaufen müssen (i> 0), geben wir 0 zurück (angenommen, alle ci> 0). Wenn i = 0 ist, haben wir keine Maschinen, die wir kaufen müssen, also ist die Zuverlässigkeit 1 (wenn es 0 wäre, dann würde alles mit 0 multipliziert werden, was nicht gut ist). Wenn noch Budget übrig bleibt (b> 0) und die Maschinen noch zu kaufen sind (i> 0), versuchen wir alle Möglichkeiten m von Maschinen vom Typ i zu kaufen - wir müssen mindestens m ≥ 1 kaufen, und bis m ≤ b ≤ Boden (b/c_i) ≤ b ≤ B, von ihnen. In jedem Fall wird das verbleibende Budget b - m · c_i sein. Die beste Zuverlässigkeit für Maschinen 1,. . ., i - 1 wird REL [i - 1, b - m · ci], was mit dem Beitrag der m Kopien von M_i multipliziert werden muss, (1 - (1 - ri)^m) oder zusammengefasst here.

Ich erkenne das viele Informationen, aber ich bin seit einer Weile jetzt fest, so dass jede Hilfe geschätzt wird.

Answer 1

Sie können mit einer einfacheren Wiederholung als das arbeiten. Für i = 0, ..., n und b = 0, ..., B lassen wir R(i, b) die maximale Zuverlässigkeit der Sub-Pipeline von Stufe 1 bis Stufe i gegeben Budget B. Die Basisfälle sind

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

da die leere Pipeline nie ausfällt und nichts kostet. Danach haben wir die verknüpfte Wiederholung, die ich etwas für Klarheit neu geschrieben haben:

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 = 0, ..., floor(b/c_i)}, 

wo k ist die Anzahl der Bühne i Maschinen, die wir kaufen erwägen (definieren 0^0 = 1 bei Maschinen können absolut zuverlässig sein, man sollte Berechnen Sie die Kraft selbst und reduzieren Sie dann auf eine Multiplikation, die dieses Problem löst und die Leistung verbessert. Der Faktor (1 - (1-r_i)^k) ist die Zuverlässigkeit einer Stufe i mit k Maschinen. Der Faktor R(i-1, b - k*c_i) ist die maximale Zuverlässigkeit der vorherigen Stufen angesichts des Restbudgets. Die Grenze floor(b/c_i) ist die maximale Anzahl der Stufen i Maschinen, die insgesamt höchstens b kosten.