0

所以，我试图在java工作中简单实现一个动态编程问题。该方法是算法的切杆法，第三版（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));
}

然后递归将终止为 is 的第一个i值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

StackOverflow 发生是因为您的循环从 0 开始：

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

n-iwhen i == 0is n，因此您不会减少递归的范围并“更接近”基数，这会导致 StackOverflow。

于 2013-08-09T07:26:34.727 回答
1 
for(int i=0;i<n;i++){
        q = Math.max( q, p[i]+cutRod(p,n-i));

看看当i = 0, cutRod(p, n) calls cutRod(p, n-0)= 无限循环时会发生什么

在无限循环中，堆栈必然会溢出，因为它的大小是有限的，这就是你最终得到 StackOverflow 的原因。

于 2013-08-09T07:27:59.233 回答
0

包 com.implement.algorithms;

导入 java.util.Arrays；

公共类 RodCut {

private static final int [] PRICE = {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
private static  int [] MAX_PRICE = new int[PRICE.length];

private static int maxPrice(int n){
    if(n == 1 ){
        return PRICE[0];
    }
    if(n == 0){
        return 0;
    }
    int currentVal = 0;
    int maxVal = 0;
    for(int i = 0; i <= n - 1 ; i++ ){
        if(MAX_PRICE[n  - 1 - i] == -1){
            MAX_PRICE[n - 1 - i] = maxPrice(n-i-1);
        }
        currentVal = PRICE[i] + MAX_PRICE[n - i -1];

        if(currentVal > maxVal){
            maxVal = currentVal;
        }
    }
    return maxVal;

}

public static void main(String[] args) {
    System.out.println(Arrays.toString(PRICE));
    Arrays.fill(MAX_PRICE, -1);
    System.out.println(maxPrice(10));
}

}

于 2013-10-02T14:47:39.423 回答
0

导入静态 java.lang.Math.max；

公共类cutrod{

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 回答