切割钢条

来自计算思维百科
跳转至: 导航搜索
切割钢条1.png

某公司出售一段长度为i英寸的钢条的价格为Pi(i=1,2...单位:美元),下面给出了价格表:

长度i

1

2

3

4

5

6

7

8

9

10

价格Pi

1

5

8

9

10

17

17

20

24

30

给定一段长度为8英寸的钢条,求切割方案,使得销售收益最大。

解决方案—动态规划法

长度为8英寸的钢条共有27种不同的切割方案,因为在距离钢条左端i(i=1,2,…7)英寸处,总是可以选择切割或不切割。

如果一个最优解将钢条切割为k段(对某个1≤k≤8),那么对于最优切割方案n=i1+i2+...+ik,也即将钢条切割为长度分别为i1,i2...ik的小段得到的最大收益为切割钢条3.png;。

对于n≥1,切割钢条4.png。其中,pn对应不切割,对于每个i=1,2,…,7,首先将钢条切割为长度为i和7-i的两段,接着求解这两段的最优切割收益ri和rn-i(每种方案的最优收益为两段的最优收益之和)。

当完成首次切割后,我们将两段钢条看成两个独立的钢条切割问题实例。通过组合两个相关子问题的最优解,并在所有可能的两段切割方案中选取组合收益最大者,构成原问题的最优解。

对于8英寸的钢条,首先我们把它切割成两段,切割方案如下表:

长度i

价格Pi

8英寸

20美元

1英寸+7英寸

1美元+17美元=18美元

2英寸+6英寸

5美元+17美元=22美元

3英寸+5英寸

8美元+10美元=18美元

4英寸+4英寸

9美元+9美元=18美元

于是,第一步选取2英寸+6英寸的方案。再把2英寸的钢条和6英寸的钢条分别看出两个子问题,分别求解最大收益切割方案。

2英寸切割方案可能如下:

长度i

价格Pi

1英寸+1英寸

2美元

2英寸

5美元

比较得知2英寸的最佳方案是不切割,该子问题求解完成。

6英寸切割方案可能如下:

长度i

价格Pi

1英寸+5英寸

1美元+10美元=11美元

2英寸+4英寸

5美元+9美元=14美元

3英寸+3英寸

8美元+8美元=16美元

6英寸

17美元

比较得知6英寸的最佳方案是不切割,该子问题求解完成。

因此,组合子问题的解得出8英寸的最佳切割方案为2英寸+6英寸。

运用的计算思维

动态规划法把大问题分成各个小问题递归解决,从而获取最优解。体现了计算思维的分解、递归的思想。

参考链接

http://www.w2bc.com/Article/28393