一、问题描述 某公司购买长钢条，将其切割后进行出售。切割钢条的成本可以忽略不计。已知卖出钢条价格表如下。求解使销售收益最大的切割方案。 价格（元） 2 5 7 9 12 14 15 19 长度
一、问题描述
某公司购买长钢条，将其切割后进行出售。切割钢条的成本可以忽略不计。已知卖出钢条价格表如下。求解使销售收益最大的切割方案。
价格（元）
2
5
7
9
12
14
15
19
长度（米）
1
2
3
4
5
6
7
8
二、初步探索
1米：1（2）
2米：2（5）
3米：3（7）
4米：2+2（10）
5米：5或2+3（12）
6米：2+2+2（15）
7米：2+5（17）
8米：2+2+2+2（20）
三、算法实现
假设a[1]、a[2]、a[3]、a[4]、a[5]、a[6]已经求解，则a[7]的求解方式为：先设置a[7]不切割的价值最大，然后与a[1]+a[6]、a[2]+a[5]、a[3]+a[4]依次比较并替换，求出最大价值。然后再从a[1]---a[7]求解a[8]。
四、代码实现
#include "stdio.h"
int main()
{
int n,i,j,m; //n 待切割钢材的长度 //m 钢材模板个数
int a[]= {0,2,5,7,9,12,14,15,19};
int b[100]= {0};
printf("请输入要切割钢材的长度：");
scanf("%d",&n);
m=sizeof(a)/sizeof(int)-1;
for(i=1; i<=n; i++)
{
if(i<=m)
b[i]=a[i];
for(j=1; j<=i; j++)
{
if(b[j]+b[i-j]>b[i])
b[i]=b[j]+b[i-j];
}
}
for(i=1; i<=n; i++)
printf("%d ",b[i]);
printf("\n%d米的钢材切割后的最大价格为%d",n,b[n]);
}五、思考和扩展
1、自下而上的解决方法
（1）、斐波拉切数列：
1、1、2、3、5、8、13、21
（2）、杨辉三角：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
（3）、钢材切割问题
2、自上而下的解决方法
（1）、递归问题如汉诺塔
3、钢材切割问题的进一步思考
（1）相对最大价值法
如：一段5米的钢材进行切割。切割的最小长度为2米。
价格（元）
5
7
9
12
14
15
19
长度（米）
2
3
4
5
6
7
8
单位长度
最大价值
2.5
2.3
2.25
2.4
2.3
2.1
2.37
求每一段钢材的单位长度最大价值→从相对单位长度最大价值开始依次切割。
该方法为一种可能的比较好的快速解法，但不一定是最优解。
（2）求具体的切割方式
目前只是求解n米的钢材切割后的最大价值，但是没有求解具体怎么切割，因此可以再进一步求解。
【文章转自 盐城网站开发公司 http://www.1234xp.com/yancheng.html 复制请保留原URL】