首页 > 代码库 > 算法导论第十五章之钢条切割问题(自底向上版本)
算法导论第十五章之钢条切割问题(自底向上版本)
#include<iostream> using namespace std; int bottom_up_cut_rod(int p[],int n,int &pos) { int *r=new int[n+1]; int *s=new int[n+1]; for(int i=0;i<=n;++i) s[i]=0; for(int i=0;i<=n;++i) r[i]=0; for(int j=1;j<=n;++j) { int q=-1; for(int i=1;i<=j;++i) { //q=q>p[i]+r[j-i]?q:p[i]+r[j-i]; if(q<p[i]+r[j-i]) { q=p[i]+r[j-i]; s[j]=i; } } r[j]=q; } pos=s[n]; return r[n]; } int main() { const int size=10 ; int p[11]={0,1,5,8,9,10,17,17,20,24,30}; int pos; int sum=bottom_up_cut_rod(p,size,pos); cout<<sum<<endl; cout<<pos<<endl; system("pause"); return 0; }
算法导论第十五章之钢条切割问题(自底向上版本)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。