Algorytm programowania dynamicznego podobny do Knapsack Java Code

Question

System produkcyjny o znaczeniu krytycznym ma n etapów, które muszą być wykonywane sekwencyjnie; etap i jest wykonywany przez maszynę M_i.

Każda maszyna M_i ma prawdopodobieństwo r_i niezawodnie działającego i prawdopodobieństwo 1-r_i awarii (a awarie są niezależne). Dlatego jeśli zaimplementujemy każdy etap z pojedynczą maszyną, prawdopodobieństwo, że cały system działa, to r_1, r_2, ..., r_n. Aby zwiększyć to prawdopodobieństwo dodajemy nadmiarowość poprzez posiadanie m_i kopii maszyny M_i, która wykonuje etap i.

Prawdopodobieństwo, że wszystkie kopie m_i zawiodą jednocześnie, wynosi tylko (1-r_i)^(m_i), więc prawdopodobieństwo, że etap i zostanie zakończony poprawnie wynosi 1- (1-r_i)^(mi) i prawdopodobieństwo, że cały system działa jako prod (i = 1, n) {1- (1-r_i)^(m_i)}.

Każda maszyna M_i ma koszt c_i, a całkowity budżet B to zakup maszyn. (Załóżmy, że B i c_i są dodatnimi liczbami całkowitymi). Napisz algorytm w kodzie Javy, który podał prawdopodobieństwa r_1, ..., r_n, koszty c_1, ..., c_n i budżet B, znajdzie zwolnienia m_1, .. ., m_n, które mieszczą się w dostępnym budżecie i maksymalizują prawdopodobieństwo, że system działa poprawnie (określić maksymalną osiągalną niezawodność). Pokaż także, ile maszyn każdego typu osiąga tę niezawodność związaną z budżetem.

Więc czytam w pliku, który daje mi całkowity budżet, a następnie liczbę maszyn, a następnie dla każdej maszyny czytam w kosztach i niezawodności. Przechowuję koszt i niezawodność na dwóch połączonych listach (nie jestem pewien, czy to jest najlepsze).

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

Stąd wiem, że jednym z każdej maszynie musi być użyta tylko raz, więc odjąć budżetu o łączną kwotę to koszt jednej z każdej maszynie (totalCostOfOneEach), to daje mi pozostało budżetu lub budżet redundancji Jeśli będziesz.

bRedundent = (budget - totalCostOfOneEach); 

Teraz jest, gdzie utknąłem, jestem zagubiony na tym, co pętli, aby znaleźć rozwiązanie. I zbadali i okazało się to solution ale nie rozumiem linię

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

Więc co wiem jest Stworzyłem podwójną tablicę i zainicjować tablice jak tak:

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

Teraz jest gdzie utknąłem, wierzę, że powinienem włączyć pętlę na liczbie komputerów, a następnie kosztach, ale to nie działa i wiem, że muszę jakoś uwzględnić budżet. Więc to, co aktualnie mam, że nie działa w ogóle:

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

Wiem subproblem oznaczamy finalRel [I, B], najbardziej niezawodny konfiguracja maszyn 1, 2. . . , i (co najmniej jedna z każdej maszyny) dostępne w ramach budżetu b. Pożądana odpowiedź będzie ostatecznaRel [n, B].

I powtarzanie się, jeśli jesteśmy w ramach budżetu, zwracamy niezawodność 0 (co nie jest możliwe). Jeśli brakuje nam budżetu (b = 0), ale wciąż trzeba kupić maszyny (i> 0), zwracamy 0 (załóżmy wszystkie ci> 0). Jeśli i = 0, nie mamy maszyn, które musimy kupić, więc niezawodność wynosi 1 (jeśli byłaby 0, to wszystko byłoby pomnożone przez 0, co nie jest dobre). Jeśli pozostanie budżet (b> 0) i maszyny do kupienia (i> 0), wypróbujemy wszystkie możliwości m maszyn typu i do kupienia - musimy kupić co najmniej m ≥ 1 i do m ≤ b ≤ podłoga (b/c_i) ≤ b ≤ B, z nich. W każdym przypadku pozostały budżet będzie wynosił b - m · c_i. Najlepsza niezawodność dla maszyn 1,. . ., i - 1 będzie REL [i - 1, b - m · ci], który musi być pomnożony przez wkład m kopii M_i, (1 - (1 - ri)^m) lub podsumowany here.

Zdaję sobie z tego mnóstwo informacji, ale utknąłem przez jakiś czas, więc każda pomoc jest doceniana.

Answer 1

Możesz pracować z prostszym nawrotem niż to. W przypadku i = 0, ..., n i b = 0, ..., B, zapewniamy R(i, b) maksymalną niezawodność pod-rurociągu od etapu 1 do etapu i z podanym budżetem B. Podstawowymi skrzynkami są

, ponieważ pusty rurociąg nigdy się nie zawiedzie i nic nie kosztuje. Następnie mamy połączoną nawrotu, co mam przepisany nieco dla jasności:

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

gdzie k jest liczba etap i maszyn, że jesteśmy rozważa zakup (określającą 0^0 = 1 w maszynach sprawa może być doskonale wiarygodne; zalecana obliczyć moc, a następnie zmniejszyć siłę do mnożenia, co rozwiązuje ten problem i poprawia wydajność). Współczynnik (1 - (1-r_i)^k) jest niezawodnością urządzeń i z urządzeniami i. Współczynnik R(i-1, b - k*c_i) jest maksymalną niezawodnością poprzednich etapów, biorąc pod uwagę pozostały budżet. Limit floor(b/c_i) to maksymalna liczba urządzeń scenicznych i, które w sumie kosztują co najwyżej b.