动态规划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;
}
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 动态规划(Dynamic Programming) 本文包括: 动态规划定义 状态转移方程 动态规划算法步骤 最长...
    廖少少阅读 3,764评论 0赞 18
  • 城市的秋天阅读 333评论 0赞 0
  • FIREFOXJS阅读 292评论 0赞 0
  • 整体介绍: Android桌面小控件称为Widget,通过AppWidgetProvider类提供,AppWidg...
    _人间客阅读 1,904评论 0赞 0
  • 有人说,酒是上天赐给人类的美味;有人说,酒是天、地、人共奏的交响曲;也有人说,酒是液体的诗歌...... 2 从古...
    易科树阅读 614评论 0赞 0

友情链接更多精彩内容