RodCutting：ロッドが配列の長さより大きい場合

Question

メソッドcutRodとbottomUpCutRodを変更して、配列の長さよりも長い長さを保持する方法を教えてください。たとえば、現在pの長さは11ですが、この配列を持つ長さ15,20などの棒をどのように切断できますか？ IはcutRod（P、10）を呼び出す場合

p = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

例えば、I 30を得るが、それはcutRod（P、15）に、もちろんクラッシュまたは cutRod（P、20）。 （bottomUpCutRodにも同じことが適用されます）。どのようにこれを行うにはどのようなアイデア？これは動的プログラミングの問題です。bottomUpCutRodメソッドを実装する私のアイデアは、pをたどることです。各要素について、それ自身とその近傍のすべての順列を計算し、必要に応じて結果の配列rを更新します。

public class Main {  
    private static final double MINUS_INFINITY = Double.NEGATIVE_INFINITY;  

    public static void main(String[] args) { 

     // price array 
     double[] p = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30}; 

     // test cutRod 
     cutRod(p,10); 

     // test bottomUpCutRod 
     bottomUpCutRod(p,10); 

    }//end of main 

    // an optimal cut for a rod of length n 
    // p is the price array 
    // use recursion 
    private static double cutRod(double[] p, int value) { 
     double[] r = new double[value+1]; 
     double out = 0; 

      // initialize r to NEGATIVE_INFINITY; 
     for (int i = 1; i < r.length; i++) 
      r[i] = MINUS_INFINITY; 

     // call the helper method 
     out = helpCutRod(p,r.length-1,r); 

     // print r 
     System.out.println("Result "); 
     System.out.println("r[" + (r.length-1) + "] = " + r[r.length-1]); 

     return out; 
    }//end of method    

    // helpCutRod computes an optimal cut for a rod 
    // p is the price array and r[i] is the optimal cut for a rod of length i 
    // n is the length of the rod that is currently being computed 

    private static double helpCutRod(double[] p, int n, double[] r) { 
     double q = MINUS_INFINITY; 
     if (r[n] >= 0) // the whole r was computed 
      return r[n]; 
     if (n == 0) 
      q = 0; 
     else { 
      for (int i = 1; i <= n; i++) {     
       q = RodCutting.max(q, p[i] + helpCutRod(p,n-i,r)); 
      }  
      r[n] = q; 
     }   
     return q; 
    }     

    // use the bottom-up approach 
    // do NOT use recursion 

    private static double bottomUpCutRod(double[] p, int len) { 
     // r[i] is the optimal cut for a rod of length i 
     double[] r = new double[len+1]; 
     r[0] = 0; 
     for (int j = 1; j < p.length; j++) { 

      // compute r[j] 
      double q = MINUS_INFINITY; 

      // r[j] is the maximum over i of p[i] + r[j-i] 
      // where 1<= i <= j 

      for (int i = 1; i <= j; i++)     
       q = max(q, p[i] + r[j-i]); 

      // update value of r[j] 
      r[j] = q; 
     }//end of for outer  

     // print r 
     System.out.println("The r array from the bottomUpCutRod:"); 
      System.out.println("r[" + len + "] = " + r[len]); 
     return r[len] ;  
    }//end of method 
    public static double max(double a, double b){ 

     if(a<=b){ 
      return b; 
     }else{ 
      return a; 
     } 
    }//end of max 
}//end of class 

Answer 1

私が正しくロッド切断の問題を理解していれば、あなたの価格配列、pは、あなたがp.length - 1を通じてlenghts 0のロッド片を販売することができた時の価格を伝えます。したがって、配列の長さが11の場合、長さ15,20、または30のインラインロッドを持っていても、長さ10までの値段を知ることができます。長さ11以上の価格はわからないので、私はそのアルゴリズムが、あなたが肯定的な価格を知っている部分にあなたの棒を切断することを期待するだろう。

これがすべて正しい場合、解決は簡単です。 、たとえば、cutRod(p, 15)を計算するには、最初の

p = Arrays.copyOf(p, 15 + 1); 

を行う。これは、15からインデックス0を持つ新しい配列にpをコピーします、zeoresで埋め。今度はあなたのメソッドを実行してください。もちろん、他の初期長さについても同様です。本変形例に

、15のロッド長のためのプログラムのプリント：

Result 
r[15] = 43.0 
The r array from the bottomUpCutRod: 
r[15] = 43.0 

私はそれが10で片、3,2得価格30 + 8 + = 43 5見つかったと仮定し、私は避難所」チェックされていません。

EDIT：棒が価格配列よりもはるかに長い場合、価格配列の最大値よりも長いカットで結果を計算させるのは無駄でしょう。したがって、上記の迅速な修正の代わりに、実際には、より短い価格配列と長い初期ロッドを受け入れるようにメソッドを変更することが可能です。再帰helpCutRod()で

にループの変更：これは、我々は価格を持っているだけの作品が考慮されることを確認します

 for (int i = 1; i <= Math.min(n, p.length - 1); i++) {     

。 bottomUpCutRod()については

、二つの変更が必要とされています

jがlenと等しくなるまで、ループの最初に実行する必要があります。

for (int j = 1; j < r.length; j++) { 

そして再び、forループの内側にはpの境界を通過しないでください。

 for (int i = 1; i <= Math.min(j, p.length - 1); i++)     

の代わりにこれらの3つの変更配列の場合、プログラムは上記と同じ結果を出力します。