动态规划cuttingRod

算法导论上的。

naive的algorithm:

#include <iostream>
#include <limits.h>
using namespace std;
int max(int a, int b)
{  return (a>b)?a:b;
}
int cutRod(int price[], int n)
{
  if(n<=0){ return 0;}
  int max_val = INT_MIN;
  for (int i = 0;i<n;i++)
  {
    max_val = max(max_val, price[i] + cutRod(price, n - i - 1));
  }
  return max_val;
}
int main(){
int arr[] = {1,5,8,9,10,17,17,20,24,30};
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"maximum: "<<cutRod(arr,9)<<endl;
return 0;
}

top-down algorithm:

#include <iostream>

#include <limits.h>

using namespace std;

int cut2(int price[],int n, int rem[]);

int max(int a, int b){
  return (a>b)?a:b;
}

int cut1(int price[],int n){
  int rem[n];
   for(int i = 0;i<=n;i++){
    rem[i] = INT_MIN;
   }
   return cut2(price,n,rem);
}

int cut2(int price[],int n, int rem[]){
  int q = INT_MIN;
  if(rem[n]>=0){
    return rem[n];
  }
  if(n == 0){
    q = 0;
  }
  else{
    q = INT_MIN;
    for(int i = 0;i<n;i++){
      q = max(q,price[i]+cut2(price,n - i - 1,rem));
    }
  }
  rem[n] = q;
  return q;
}
int main(){
  int arr[] = {1,5,8,9,10,17,17,20,24,30};
  int result = cut1(arr,9);
  cout<<result<<endl;
  return 0;
}