Thuật toán lập trình động tương tự như mã Java Knapsack

Question

Một hệ thống sản xuất nhiệm vụ quan trọng có n giai đoạn phải được thực hiện tuần tự; giai đoạn i được thực hiện bởi máy M_i.

Mỗi máy M_i có xác suất r_i hoạt động đáng tin cậy và xác suất 1-r_i của lỗi (và các lỗi không phụ thuộc). Do đó, nếu chúng ta thực hiện từng giai đoạn với một máy đơn lẻ, xác suất mà toàn bộ hệ thống hoạt động là r_1, r_2, ..., r_n. Để cải thiện xác suất này, chúng tôi thêm dự phòng, bằng cách có m_i bản sao của máy M_i thực hiện giai đoạn i.

Xác suất tất cả các bản sao m_i không đồng thời chỉ là (1-r_i)^(m_i), do đó xác suất mà giai đoạn i hoàn thành chính xác là 1- (1-r_i)^(mi) và xác suất toàn bộ hệ thống hoạt động là prod (i = 1, n) {1- (1-r_i)^(m_i)}.

Mỗi máy M_i có chi phí c_i và có tổng ngân sách B để mua máy. (Giả sử rằng B và c_i là số nguyên dương.) Viết thuật toán trong mã java có xác suất r_1, ..., r_n, chi phí c_1, ..., c_n và ngân sách B, tìm số dư thừa m_1, .. ., m_n nằm trong ngân sách có sẵn và tối đa hóa xác suất mà hệ thống hoạt động chính xác (xác định độ tin cậy tối đa có thể đạt được). Ngoài ra, hiển thị số lượng máy của mỗi loại đạt được độ tin cậy đó trong phạm vi ngân sách.

Vì vậy, tôi đọc trong một tệp cung cấp cho tôi tổng ngân sách cho phép, tiếp theo là số lượng máy móc, và sau đó cho mỗi máy tôi đọc chi phí và độ tin cậy. Tôi lưu trữ các chi phí và độ tin cậy vào hai danh sách liên kết (không chắc chắn nếu điều này là tốt nhất).

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

Từ đó tôi biết rằng một trong mỗi máy phải được sử dụng một lần nên tôi trừ ngân sách bằng tổng số tiền chi phí cho một trong mỗi máy (totalCostOfOneEach), điều này mang lại cho tôi còn sót lại ngân sách hoặc ngân sách dự phòng nếu bạn muốn.

bRedundent = (budget - totalCostOfOneEach); 

Bây giờ là nơi tôi bị kẹt, tôi bị mất trên những gì để lặp lại để tìm giải pháp. Tôi đã nghiên cứu và phát hiện này solution nhưng tôi không hiểu dòng

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

Vì vậy, những gì tôi biết là tôi đã tạo ra một mảng đôi và tôi khởi tạo các mảng như vậy:

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

Bây giờ là nơi tôi bị mắc kẹt, tôi tin rằng tôi nên lặp lại số lượng máy và sau đó chi phí nhưng điều này là không làm việc và tôi biết tôi cần kết hợp ngân sách bằng cách nào đó. Vì vậy, đây là những gì tôi hiện có mà không hoạt động ở tất cả:

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

Tôi biết biểu tượng con được biểu thị finalRel [i, b], cấu hình đáng tin cậy nhất của máy 1, 2,. . . , i (ít nhất một trong mỗi máy) có sẵn trong ngân sách b. Câu trả lời mong muốn sẽ là finalRel [n, B].

Và sự lặp lại nếu chúng tôi không đủ ngân sách, chúng tôi trả về độ tin cậy 0 (có nghĩa là không thể). Nếu chúng ta hết ngân sách (b = 0), nhưng vẫn cần mua máy (i> 0), chúng ta trả về 0 (giả sử tất cả ci> 0). Nếu i = 0, chúng ta không có máy móc mà chúng ta phải mua, vì vậy độ tin cậy là 1 (nếu nó là 0, thì mọi thứ sẽ được nhân với 0, điều đó là không tốt). Nếu có ngân sách còn lại (b> 0) và các máy còn lại để mua (i> 0), chúng tôi thử tất cả các khả năng m của máy loại i để mua - chúng tôi phải mua ít nhất m ≥ 1 và tối đa m ≤ b ≤ sàn (b/c_i) ≤ b ≤ B, trong số đó. Trong mỗi trường hợp, ngân sách còn lại sẽ là b - m · c_i. Độ tin cậy tốt nhất cho máy 1,. . ., i - 1 sẽ là REL [i - 1, b - m · ci], cần được nhân với sự đóng góp của các bản sao m của M_i, (1 - (1 - ri)^m) hoặc tóm tắt here.

Tôi nhận ra điều này rất nhiều thông tin nhưng tôi đã bị mắc kẹt trong một thời gian vì vậy mọi trợ giúp đều được đánh giá cao.

Answer 1

Bạn có thể làm việc với sự lặp lại đơn giản hơn thế. Đối với i = 0, ..., n và b = 0, ..., B, chúng tôi cho phép R(i, b) là độ tin cậy tối đa của kênh phụ từ giai đoạn 1 đến giai đoạn i ngân sách đã cho B. Các trường hợp cơ sở là

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

vì đường ống trống không bao giờ bị lỗi và không mất phí. Sau đó chúng ta có tái phát liên kết, mà tôi đã viết lại một chút cho rõ ràng:

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

nơi k là số giai đoạn i máy mà chúng tôi đang cân nhắc mua (xác định 0^0 = 1 trong trường hợp máy có thể được hoàn toàn đáng tin cậy, bạn nên tự tính toán sức mạnh của mình và sau đó giảm sức mạnh cho phép nhân, giải quyết vấn đề này và cải thiện hiệu suất). Các yếu tố (1 - (1-r_i)^k) là độ tin cậy của một giai đoạn i với k máy. Các yếu tố R(i-1, b - k*c_i) là độ tin cậy tối đa của các giai đoạn trước đó cho ngân sách còn lại. Giới hạn floor(b/c_i) là số lượng tối đa của giai đoạn i máy có tổng chi phí tối đa là b.