ナップザックJavaコードに類似した動的プログラミングアルゴリズム

Question

ミッションクリティカルなプロダクションシステムは、n個のステージを逐次実行する必要があります。ステージiは機械M_iによって実行される。

各マシンM_iは、確実に機能する確率r_iと、失敗の確率1-r_i（およびその失敗は独立している）とを有する。したがって、各ステージを1台のマシンで実装すると、システム全体が動作する確率はr_1、r_2、...、r_nになります。この確率を向上させるために、ステージiを実行するマシンM_iのm_i個のコピーを有することによって、冗長性を追加する。

すべてのm_iコピーが同時に失敗する確率は、（1-r_i）^（m_i）であるため、ステージiが正しく完了する確率は1-（1-r_i）^（mi）システム全体の仕事はprod（i = 1、n）{1-（1-r_i）^（m_i）}である。

各マシンM_iにはコストc_iがあり、マシンを購入するための合計予算Bがあります。 （Bとc_iは正の整数であると仮定します）確率r_1、...、r_n、コストc_1、...、c_nと予算Bを与えられたjavaコードでアルゴリズムを記述し、冗長m_​​1 ,. m_nは、利用可能な予算内であり、システムが正しく動作する確率を最大にする（達成可能な最大の信頼性を決定する）。また、各タイプのマシンが予算内でその信頼性を達成するかどうかを示します。

私は許可された総予算とその後のマシン数、次にコストと信頼性を読み込んだ各マシンのファイルを読みました。私はコストと信頼性を2つのリンクされたリストに格納します（これが最善かどうかはわかりません）。

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

そこから私は、私はそれが各マシンの1のコストの合計額（totalCostOfOneEach）で予算を引くように、各マシンの一つが一度使用されなければならないことを知って、これは私が予算や冗長予算上の左できますあなたがするならば。私は立ち往生午前どこ

bRedundent = (budget - totalCostOfOneEach); 

は今、私は解決策を見つけるためにどのようなループを超えるまでに失われています。私が研究し、このsolutionを見つけましたが、私はライン私は二重の配列を作成しているされて知っているものをそう

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

を理解していないと私はように配列を初期化している：

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

が今あります私は立ち往生していますが、私はマシンの台数とコストをループする必要があると信じていますが、これは機能していません。何とか予算を組み込む必要があることがわかります。私は部分問題がfinalRel [I、B]、マシン1、2の最も信頼性の高い構成では、表記されて知っている

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（各マシンの少なくとも1台）は予算内で利用可能です。希望の答えはfinalRel [n、B]になります。

私たちが予算を下回っている場合は、信頼性0（意味できません）を返します。予算外（b = 0）でもマシンを購入する必要がある場合（i> 0）、0を返します（ci> 0と仮定します）。 i = 0の場合、購入する必要がないマシンがあるので、信頼性は1です（0の場合はすべてが0で乗算されます）。予算が残っており（i> 0）、i型のマシンのすべての可能性を試す - 少なくともm≥1で、m≤bまで購入する必要がある≤床（b/c_i）≦b≦Bである。いずれの場合も、残りの予算はb-m・c_iになります。マシン1、。 。 。m_i、（1 - （1 - ri）^ m）のm個のコピーの寄与によって掛け合わされるか、要約されたhereであるREL [i-1、b-m・ci]である。

私はこれに多くの情報があることを認識していますが、私はしばらくの間立ち往生していますので、何か助けに感謝します。

Answer 1

より簡単な反復で作業できます。 i = 0, ..., nおよびb = 0, ..., Bについては、Bのステージ1からステージiまでのサブパイプラインの最大信頼度をR(i, b)とします。ベースケースは、空のパイプラインが失敗することはなく、費用もかからないので、

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

です。 ;あなたがすべき

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

kはケース・マシンで 0^0 = 1を定義し、我々は購入を検討しているマシンが（完全に信頼性の高いことができ、ステージ iの数である

：その後、私たちは、私はわかりやすくするために、わずかに書き直されているリンク再発を持っています自分でパワーを計算し、強度を減らして乗算すると、この問題が解決され、パフォーマンスが向上します）。ファクタ(1 - (1-r_i)^k)は、kマシンのあるステージiの信頼性です。係数R(i-1, b - k*c_i)は、残余予算が与えられた場合の前段階の最大信頼度です。制限floor(b/c_i)は、合計でbになるステージiマシンの最大数です。