本文主要是介绍钢铁切割问题 动态规划（输出切割方案和带成本的解法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述：
假定我们知道sering公司出售一段长度为I英寸的钢条的价格为pi(i=1,2,3….)钢条长度为整英寸如图给出价格表的描述
| 长度i | 1 | 2 | 4 | 5 | 6 | 7 | 8 | 9 |
| 价格p[i] | 1 | 5 | 9 | 10 | 17 | 17 | 20 | 24 |
这个题不说什么递归算法复杂度有多高的什么的问题了，就直接说一下动态规划，首先我们这样想这个题，就是把长度为i英寸的钢条切割，首先切一刀会切成两部分，或者不切。现在就比较这两种情况哪种的收益高（切或者不切），如果不切收益高，那么结果直接就是不切的收益，如果切成两部分，那么这两部分又可以看成是有两个不同长度的钢条，每一个钢条接着按这个方法讨论。这种方法其实就是动态规划的自底向上法。这种方法一般需要且当定义子问题“规模”的概念，是的任何子问题的求解都只依赖于“更小的”自问题的求解。因而我们可以将子问题按规模排序，按由小到大的顺序进行求解。当求某个子问题时，它所依赖的哪些更小的子问题都已经求解完毕，结果已经保存。每个子问题斗智求解一次，当我们求解它时，它的所有前提子问题都以求解完成。下面先给出这个题的代码，然后再做详细解释：
#include<iostream>
#include<cstdio>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int p[10010];
int r[10010];
int s[10010];
int n;int bottom_up_cut_rod(int p[],int n)
{for(int i=0;i<=n;i++) r[i]=0;int q;for(int j=1;j<=n;j++){q=-inf;for(int i=1;i<=j;i++){if(q<p[i]+r[j-i]){q=p[i]+r[j-i];s[j]=i;}}r[j]=q;}return r[n];
}int print_cut(int p[],int n,int s[])
{while(n>0){printf("%d ",s[n]);n=n-s[n];}cout<<endl;
}int main()
{int num;cout<<"请输入钢条收益"<<endl;cin>>num;for(int i=1;i<=num;i++) scanf("%d",&p[i]);cout<<"请输入钢条长度:\n"<<endl;while(~scanf("%d",&n)){cout<<"最大收益是："<<bottom_up_cut_rod(p,n)<<endl;cout<<"切割方案为： ";print_cut(p,n,s);cout<<endl;cout<<"请输入钢条长度：\n"<<endl;}return 0;
}
最后附上算法导论15.1-3加固定成本的问题解：
#include<iostream>
#include<cstdio>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int p[10010];
int r[10010];
int s[10010];
int n;int bottom_up_cut_rod(int p[],int n,int c)
{for(int i=0;i<=n;i++) r[i]=0;int q;for(int j=1;j<=n;j++){q=-inf;for(int i=1;i<=j;i++){if(q<(p[i]+r[j-i]-c*(j!=i))){q=(p[i]+r[j-i]-c*(j!=i));s[j]=i;}}r[j]=q;}return r[n];
}int print_cut(int p[],int n,int s[])
{while(n>0){printf("%d ",s[n]);n=n-s[n];}cout<<endl;
}int main()
{int num,c;cout<<"请输入钢条收益"<<endl;cin>>num;for(int i=1;i<=num;i++) scanf("%d",&p[i]);cin>>c;cout<<"请输入钢条长度:\n"<<endl;while(~scanf("%d",&n)){cout<<"最大收益是："<<bottom_up_cut_rod(p,n,c)<<endl;cout<<"切割方案为： ";print_cut(p,n,s);cout<<endl;cout<<"请输入钢条长度：\n"<<endl;}return 0;
}这篇关于钢铁切割问题 动态规划（输出切割方案和带成本的解法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
