0

だから、動的プログラミングの問題をJavaで簡単に実装しようとしています。メソッドは、アルゴリズムのカットロッド法、第 3 版 (Rivest らによる) 第 15 章 ここに私のコードがあります -

public static double cutRod(double[] p, int n){
    if(n==0)return 0;
    double q = -1000;
    for(int i=0;i<n;i++){
        q = Math.max( q, p[i]+cutRod(p,n-i));
    }
    return q;
}

public static void main(String[] args) throws FileNotFoundException, IOException{
    double[] p = {1,5,8,9,10,17,17,20,24,30};
    double val = cutRod(p,10);
    System.out.println(val);
}

これを実行しようとすると、スタック オーバーフロー エラーが発生します。デバッグしようとしても (netbeans を使用しています)、最初の再帰呼び出しでしばらく停止し、スタック オーバーフロー エラーが発生します。何か案は？

4

7 に答える 7

2

正しい方向に向けるために、 for ループを検討してください。i=0 の場合、すべての呼び出しで同じ n が cutRod に渡され、再帰が終了することはありません。

于 2013-08-09T07:26:19.790 に答える
2

nループの最初の繰り返しで、まったく同じ値で再帰を呼び出します。

for(int i=0;i<n;i++){
    q = Math.max( q, p[i]+cutRod(p,n-i));
}

その後、同じ呼び出しをもう一度呼び出しますi=0。cutRod(p,n-0)これにより、無限ループが発生します。

ループを次のように変更した場合:

for(int i=1;i<=n;i++){
    q = Math.max( q, p[i]+cutRod(p,n-i));
}

その後、再帰はiisの最初の値として終了します1。

于 2013-08-09T07:26:28.847 に答える
2

cutRoad(n) を、長さ n のロッドに必要な (可能な限り最良の) 値とします。cutRod(n) は次のように記述できます。

cutRod(n) = max(price[i] + cutRod(n-i-1)) for all i in {0, 1 .. n-1}.

そうでn-i-1はないはずn-iです。

            q = Math.max( q, p[i]+cutRod(p,n-i-1));

こちらをご参照ください

于 2013-08-09T07:29:07.310 に答える
1

ループが 0 から始まるため、StackOverflow が発生します。

for(int i=0;i<n;i++){
    q = Math.max( q, p[i]+cutRod(p,n-i));
}

n-iwhen i == 0isnであるため、再帰の範囲を縮小せず、ベースに「近づき」、StackOverflow が発生します。

于 2013-08-09T07:26:34.727 に答える
0

import static java.lang.Math.max;

パブリッククラスカットロッド{

private static int q;
private static int[] p = {0,1,5,8,9,10,17,17,20,24,30};
private static int[] r = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};

public static int cutrod_aux(int[] p, int n, int[] r){

 if (r[n]>=0){return r[n];}
 if (n==0)   return q=0;
 for(int i = 1; i <= n;i++){
     q = max(q,p[i]+cutrod_aux(p,n-i,r));
         }
r[n]=q;
return q;
}

public static void main(String[] args) {

   cutrod_aux(p, 10, r);   
}

}

于 2014-05-11T11:05:46.440 に答える