如何高效切割大量不同规格的钢材？

本文共计1139个文字，预计阅读时间需要5分钟。

问题描述：某公司购买长条形钢材，将其切割后进行销售。切割过程中，钢材的原材料成本可以忽略不计。已知销售出的钢材价格及长度如下表所示，求切割方案，使得销售收益最大。

价格（元） | 长度（米）--------- | --------

2| 5

5| 7

7| 9

9| 12

12| 14

14| 15

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米的钢材切割后的最大价值，但是没有求解具体怎么切割，因此可以再进一步求解。