本文共 5128 字，大约阅读时间需要 17 分钟。
切割钢锯条售卖
题目描述：给定一段长度为n英寸的钢条和一个价格表，求切割方案，使销售收益Rn最大。
注：若长度为n英寸的钢条的价格Pn足够大，最优解可能就是完全不需要切割。| 长度（i） | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 价格（R） | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30 |
给定一个长度为n的钢条，该钢条经过有效切割，最多能卖出多少钱？
题目分析
在最初分析本题局部最优解的时候，陷入了误区，一直在考虑局部最优解是以分割1、2、3……段来达到最后结果，后来发现这样分析走入了误区。
本题的局部最优解：长度为i的钢条最多可卖多少钱ri 长度为n的钢条的最大收益：情况1：不切割，一整条出售的价格pn；
情况2：将钢条分割成长度 i 和 j 两段的最大收益，ri+rj；
以长度为 4 举例：
从上述图中的分析可以看到方案C收益最大，即长度为4的锯条分成两段，每段的长度为2，收益是最大的（收益为10）。
长度为n英寸的钢条共有2^(n-1)种不同切割方案，因为在距离钢条左端 i (i=1, 2, … , n-1)英寸处，总是可以选择切割或者不切割。用普通的加法符号表示切割方案，因此7=2+2+3表示将长度为7的钢条切割为3段：2英寸，2英寸，3英寸。
若一个最优解将钢条切割为k段（1≤k≤n），那么最优切割方案 n = i1 + i2 + … + ik.
将钢条切割为长度分别为i1, i2, … , ik的小段，得到的最大收益为 Rn = Pi1 + Pi2+…+Pik
对于上面表格的价格样例，可以观察所有最优收益值Ri (i: 1~10)以及最优方案：
长度为1：切割方案1=1（无切割）。最大收益R1 = 1
长度为2：切割方案2=2（收益5），1+1=2（收益2）。最大收益R2 = 5
长度为3：切割方案3=3（收益8），1+2=3（收益6），2+1=3（收益6）。最大收益8
长度为4：切割方案4=4（收益9），1+3=4（收益9），2+2=4（收益10），3+1=4（收益9），1+1+2=4（收益7），1+2+1=4（收益7），2+1+1=4（收益7），1+1+1+1=4（收益4）。最大收益10
长度为5：切割方案5=5（10），1+4=5（10），2+3=5（13），1+1+3=5（10），2+2+1=5（11），1+1+1+1+1=5（5），其他是前面的排列。最大收益13
依次求出。。。
更一般的，对于Rn(n≥1)，可以用更短的钢条的最优切割收益来描述它：
Rn = max(Pn, R1+Rn-1, R2 + Rn-2, … , Rn-1 + R1)
第一个参数Pn对应不切割，直接出售长度为n的方案。
其他n-1个参数对应n-1种方案。对每个i=1,2,….,n-1，将钢条切割为长度为i和n-i的两段，接着求解这两段的最优切割收益Ri和Rn-i;(每种方案的最优收益为两段的最优收益之和)。 由于无法预知哪种方案会获得最优收益，必须考察所有可能的 i ，选取其中收益最大者。若不切割时收益最大，当然选择不切割。注意到：
为了求解规模为n的原问题，先求解子问题（子问题形式完全一样，但规模更小）。 即首次完成切割后，将两段钢条看成两个独立的钢条切割问题实例。 通过组合两个相关子问题的最优解，并在所有可能的两段切割方案中获取收益最大者，构成原问题的最优解。 称钢条切割问题满足最优子结构性质：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。
除上述解法，问题可化简为一种相似的递归：从左边切割下长度为 i 的一段，只对右边剩下的长度为 n-i 的一段进行继续切割（递归求解），对左边一段则不再进行切割。
即问题分解的方式为：将长度为n的钢条分解为左边开始一段，以及剩余部分继续分解的结果。（这样，不做任何切割的方案可以描述为：第一段长度为n，收益为Pn，剩余部分长度为0，对应收益为R0 = 0）。于是得到上面公式的简化版本：
在此公式中，原问题的最优解只包含一个相关子问题（右端剩余部分的解），而不是两个。
算法设计（递归实现）
package com.bean.algorithmbasic;public class CutRob { public static int[] prices = { 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 }; public static int solution(int length) { if (length == 0) return 0; int result = Integer.MIN_VALUE; for (int i = 1; i <= length; i++) { result = Math.max(result, prices[i - 1] + solution(length - i)); } return result; } public static void main(String[] args) { long startTime = System.currentTimeMillis(); for (int i = 1; i <= prices.length; i++) System.out.println("长度为" + i + "的最大收益为：" + solution(i)); long endTime = System.currentTimeMillis(); System.out.println("程序运行耗时(ms): " + (endTime - startTime)); }} 运行结果：
长度为1的最大收益为：1
长度为2的最大收益为：5 长度为3的最大收益为：8 长度为4的最大收益为：10 长度为5的最大收益为：13 长度为6的最大收益为：17 长度为7的最大收益为：18 长度为8的最大收益为：22 长度为9的最大收益为：25 长度为10的最大收益为：30 程序运行耗时(ms): 1当给出的锯条长度更大时，递归求解的速度已经非常慢了。慢到几乎不能接受。
下面来看下用DP怎么来解决钢条切个问题。
算法设计（动态规划实现—DP）
带备忘的自顶向下法（top-down with memoization）
此方法仍然按照自然的递归形式编写过程，但是过程会保存每个子问题的解（通常保存在一个数组或散列表中）。 当需要一个子问题的解时，过程首先检查是否已经保存过此解， 如果是，则直接返回保存的值，从而节省了计算时间； 否则，按照通常方式计算这个子问题。package com.bean.algorithmbasic;import java.util.Arrays;public class CutRobDP { public static int[] prices = { 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 }; /** 自顶向下 */ public static int mem_cut_rod(int n) { int[] dp = new int[n + 1]; // 辅助数组dp Arrays.fill(dp, Integer.MIN_VALUE); // 初始化为负无穷 return mem_cut_rod_aux(n, dp); } /** 自顶向下法的辅助函数 */ private static int mem_cut_rod_aux(int n, int[] dp) { if (dp[n] >= 0) return dp[n]; // 如果子问题已经解过，直接返回 int max = Integer.MIN_VALUE; if (n == 0) max = 0; // 如果长度为0，则最大收益为0 else { // 长度若不为0 for (int i = 1; i <= n; i++) // 找到最大收益 max = Math.max(max, prices[i - 1] + mem_cut_rod_aux(n - i, dp)); } dp[n] = max; // 把计算得到的最大收益存入结果 return max; // 返回结果 } public static void main(String[] args) { long startTime=System.currentTimeMillis(); for (int i = 1; i <= prices.length; i++) System.out.println("长度为" + i + "的最大收益为：" + mem_cut_rod(i)); long endTime=System.currentTimeMillis(); System.out.println("程序运行耗时(ms): "+(endTime-startTime)); }} 自底向上法（bottom-up method）
该方法一般需要恰当定义子问题“规模”的概念，使得任何子问题的求解都只依赖于“更小的”子问题的求解。 因而可以将子问题按规模排序，按由小到大的顺序进行求解。 当求解某个子问题时，所依赖的那些更小的子问题都已经求解完毕，结果已经保存。 每个子问题只求解一次，当求解它时（也是第一次遇到它），所有前提子问题都已经求解完成。 两种方法得到的算法具有相同的渐进运行时间，仅有的差异是在某些特殊情况下，自顶向下方法并未真正递归地考察所有可能的子问题。
由于没有频繁的递归调用开销，自底向上的复杂度函数通常具有更小的系数。package com.bean.algorithmbasic;public class CutRobDP2 { public static int[] prices = { 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 }; /** 自底向上法 */ private static int bottom_up_cut_rod(int n) { int[] dp = new int[n + 1]; dp[0] = 0; for (int j = 1; j <= n; j++) { int max = Integer.MIN_VALUE; for (int i = 1; i <= j; i++) { max = Math.max(max, prices[i - 1] + dp[j - i]); } dp[j] = max; } return dp[n]; } public static void main(String[] args) { long startTime = System.currentTimeMillis(); for (int i = 1; i <= prices.length; i++) System.out.println("长度为" + i + "的最大收益为：" + bottom_up_cut_rod(i)); long endTime = System.currentTimeMillis(); System.out.println("程序运行耗时(ms): " + (endTime - startTime)); }} （完）