c++ - 杆切割 - 递归

Question

问题:http://www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/

我的代码:http://ideone.com/HGXk3t

我尝试解决递归问题，但得到了意想不到的结果。 对于切杆问题，我最多对同一递归函数进行两次调用:一个使用该索引，另一个不使用该索引的价格。 但答案并不是应该的。 提前致谢。

#include<stdio.h>

// A utility function to get the maximum of two integers
int max(int a, int b) { return (a > b)? a : b;}

/* Returns the best obtainable price for a rod of length n and
   price[] as prices of different pieces */
int cutRod(int price[], int n, int i)
{
    if(n<1 || i==0)
        return 0;

    return max(price[i-1] + cutRod(price,n-(i+1),i), cutRod(price,n,i-1));
}

/* Driver program to test above functions */
int main()
{
    int arr[] = {17, 17, 1};
    int size = sizeof(arr)/sizeof(arr[0]);
    printf("Maximum Obtainable Value is %d\n", cutRod(arr, size, size));
    getchar();
    return 0;
}

Answer 1

您的递归调用在下降/上升过程中丢失信息。

在返回调用期间，由于它在数组中向后工作，因此它所做的就是返回最大可能值并忽略剩余的卡盘。

假设这个极端的例子，其中 n=2; 和 p=[100,1];。理想情况下，答案是 200。

第一次调用时，返回值为return max(1,cutRod(2,2-1));。 第一次调用 cutRod(2,2-1) 的第二个参数忽略杆的第二个卡盘，并开始在递归调用中检查杆的第一个卡盘。

第二级调用给出 max(100,cutRod(2,1-1));

第三次调用 i=0，因此 cutRod(2,0) = 0。

检查递归调用的级别，我们只取这对值中的最大值:

level 3 = 0 //0 comes from cutRod(2,1-1)
level 2 = max(100,0) //100 comes from cutRod(2,2-1): 0 comes from cutRod(2,1-1)
level 1 = max(1,100) //1 comes from p[2-1]: 100 comes from max(100,0)

因此 100 最终成为最大值，而不是回电时的 200

return max(price[i-1] + cutRod(price,n-(i+1),i), cutRod(price,n,i-1));

我不推荐使用这种多次递归调用的方式来解决这个动态编程问题。相反，这是在中找到的示例 算法简介， 第三版 Cormen、Leiserson、Rivest、Stein 第 363 页

#include <limits.h>
//p is the price array
//n is the initial size of the array or 'rod'
int cutRod(int p[],int n){
  if(n == 0){
    return 0;
  }
  int q = INT_MIN;
  for(int i = 1; i<=n; i++){
    q = max(q,p[i-1]+cutRod(p,n-i));
  }
  return q;
}

不带 for 循环的递归解决方案 *需要分析

//p is the price array, n is the size of the array/rod, i is index initial called with 0
int cutRod(int p[],int n,int i){
  if(n<=0 || i>=n){
    return 0;
  }
  return max(p[i]+cutRod(p,n-(i+1),0),cutRod(p,n,i+1));
}