这道题在算法导论(第三版)的204页
钢条切割问题是这样的:
给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,…,n),求切割钢条方案,使得销售收益rn最大。注意,如果长度为n英寸的钢条的价格pn足够大,最优解可能就是完全不需要切割。
假设有一张价格表为:
长度i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
价格pi | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30 |
基本思路:我们将钢条从左边切割下长度为i的一段,只对右边剩下的长度为n-i的一段继续进行切割(递归求解),对左边的一段则不再进行切割。则可得公式:
其中pi为左边长度为i的钢条的收益,rn-i为右边长度为n-i的钢条继续切割后得到的最优收益,rn为长度为n的钢条切割后得到的最优收益。
递归实现代码如下:
package dynamic;
/*
* 钢条切割 算法导论P204
*/
public class Steel {
/**
* 比较大小
* @param a
* @param b
* @return
*/
public static int max(int a, int b) {
return (a > b ? a : b);
}
/**
*
* @param p 存储价格的数组,p从0开始存储
* @param n 钢条长度为n
* @return 返回长度为n的钢条切割后得到的最大收益
*/
public static int cut(int[] p,int n){
//如果长度为0,则0收益
if(n==0)
return 0;
int q = -1;
// 思路:
//将长度为n的钢条从左切割长度为i的一段,则右端为长度为n-i的一段
//其中长度为i的左端不继续切割,只继续切割右端的那一部分
//一直递归的cut(p,n-i)最后得到的是长度为n-i的钢条切割后的最大收益
for(int i = 0; i < n; i++) {
q = max(q,p[i] + cut(p,n-i-1)); //切割后的收益和不切割
}
return q;
}
public static void main(String[] args) {
int[] p = {1,5,8,9,10,17,17,20,24,30};
int n = 4;
System.out.println(cut(p,n));
}
}
因为这道题是用递归实现的,所以必然存在一个缺点,那就是当数据n很大时,方法cut会反复调用相同的参数值对自身进行递归调用,即它反复求解相同的子问题。这会导致cut方法运行时间为n的指数函数。效率很低!
所以我们需要进行优化,可以使用动态规划法来求解最优钢条切割问题。
如何利用动态规划法来求解最优钢条切割问题请见下文。
版权声明:本文为hjl_heart原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。