算法|动态规划之切割钢条算法|Java

假设公司出售一段长度为i英寸的钢条的价格为Pi（i = 1, 2, ...单位：美元），下面给出了价格表样例：
长度i12345678910
价格Pi1589101717202430
切割钢条的问题是这样的：给定一段长度为n英寸的钢条和一个价格表Pi，求切割方案，使得销售收益Rn最大。
当然，如果长度为n英寸的钢条价格Pn足够大，最优解可能就是完全不需要切割。
对于上述价格表样例，我们可以观察所有最优收益值Ri及对应的最优解方案：
R1 = 1，切割方案1 = 1（无切割）
R2 = 5，切割方案2 = 2（无切割）
R3 = 8，切割方案3 = 3（无切割）
R4 = 10，切割方案4 = 2 + 2
R5 = 13，切割方案5 = 2 + 3
R6 = 17，切割方案6 = 6（无切割）
R7 = 18，切割方案7 = 1 + 6或7 = 2 + 2 + 3
R8 = 22，切割方案8 = 2 + 6
R9 = 25，切割方案9 = 3 + 6
R10 = 30，切割方案10 = 10（无切割）
更一般地，对于Rn（n >= 1），我们可以用更短的钢条的最优切割收益来描述它：
Rn = max(Pn, R1 + Rn-1, R2 + Rn-2,...,Rn-1 + R1)
首先将钢条切割为长度为i和n - i两段，接着求解这两段的最优切割收益Ri和Rn - i
（每种方案的最优收益为两段的最优收益之和），由于无法预知哪种方案会获得最优收益，
我们必须考察所有可能的i，选取其中收益最大者。如果直接出售原钢条会获得最大收益，
我们当然可以选择不做任何切割。
分析到这里，假设现在出售8英寸的钢条，应该怎么切割呢？
代码如下：

package 动态规划; /** * 钢条不同长度价格不同，求如何切割钢条卖出最划算 * 用到动态规划 * @author wangdong20 * */public class Steel { /** * 自底向上非递归方法解决钢条切割问题， * 不仅保存最优收益值，还保存对应的切割方案 * @param p 不同长度钢条的价格 * @param n 钢条的总长度 */ public static int[][] extendedBottomUpCutRod(int[] p, int n){ /*if(n == 0){ return new int[][]{ {0}, {0}}; }*/ int[][] s = new int[2][n + 1]; // s[0][2]保存2米长钢条的最佳收益，s[1][2]保存2米长钢条的切割方案 s[0][0] = 0; for(int j = 1; j <= n; j++){ int q = -99999; for(int i = 1; i <= j; i++){ if(q < p[i] + s[0][j - i]){ q = p[i] + s[0][j - i]; s[1][j] = i; } } s[0][j] = q; } System.out.print("\n最终受益: " + s[0][n]); return s; } /** * 根据算法打印出长度为n的钢条完整的最优切割方案 * @param p 不同长度钢条的价格 * @param n 钢条的总长度 */ public static void printCutRodSolution(int[] p, int n){ int result[][] = extendedBottomUpCutRod(p, n); System.out.print("\n钢板切除方案: "); while(n > 0){ System.out.print(result[1][n] + " "); n = n - result[1][n]; } } /** * @param args */ public static void main(String[] args) { // TODO 自动生成方法存根 //钢条的价格price[0]表示0米长钢条的价格，price[5]代表5米长钢条的价格 int price[] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30}; System.out.println("The price: "); for(Integer i : price){ System.out.print(i + " "); }printCutRodSolution(price, 8); }}

运行结果如下：
【算法|动态规划之切割钢条】The price:
0 1 5 8 9 10 17 17 20 24 30
最终受益: 22
钢板切除方案: 2 6