动态规划实现钢条切割问题
动态规划算法的步骤
1. 刻画一个最优解的结构特征；
2. 递归地定义最优解的值；
3. 计算最优解的值；
4. 利用计算出的信息，构造一个最优解。
钢条切割问题描述
(1)Serling公司购买长钢条，将其切割为短钢条出售。不同的切割方案，收益是不同的，怎么切割才能有最大的收益呢？假设，切割工序本身没有成本支出。 假定出售一段长度为i英寸的钢条的价格为p i （i=1,2,…）。钢条的长度为n英寸。如下给出一个价格表P。
给定一段长度为n英寸的钢条和一个价格表P，求切割钢条方案，使得销售收益 rn 最大。(如果长度为n英寸的钢条的价格p n 足够大，则可能完全不需要切割，出售整条钢条是最好的收益)
(2)简单给出一个例子
考虑n=4的时候。如图所示给出4英寸的钢条可能的切割方案
8种切割方案，根据图中的价格表，可以看书最优策略是方案c(将钢条切割为两段长度为2英寸的钢条–收益为10)
(3)长度为n英寸的钢条共有2 n-1 中不同的切割方案。
如果一个最优解将总长度为n的钢条切割为k段，每段的长度为i ,j（1≤j≤k），则有：n=i 1 +i 2 +…+i k
得到的最大收益为：r n =p i1 +p i2 +…+p ik
(4)对上述价格表样例，我们可以观察出所有最优收益值以及对应的切割方案
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=2+6
r10=30; 切割方案10=10(无切割)
(5)对于长度为n（n≥1）的钢条，设r n 是最优切割的收益对最优切割，若其首次切割在位置i，钢条被分成长度为i和n-i的两段，有：r n= r i + r n-i
一般情况，任意切割点j都将钢条分为两段，长度分别为j和n-j，1≤j≤n。令r j 和r n-j 分别是这两段的最优切割收益，则该切割可获得的最好收益是：r’ n = r j + r n-j所以有
钢条切割问题的递归求解过程
(1)钢条从左边切割下长度为i的一段，然后只对右边剩下的长度为n-i的一段继续进行切割（递归求解),这个时候有
(2)自顶向下的递归实现
(3)但是这种算法在n比较大的情况下效率低，因为总是求解相同的子问题，反复的进行自身递归调用。如图是子问题规模为n=4的情况
这棵树显示了n=4 的时候的递归调用过程，每个结点的标号为对应的子问题规模n。这可递归调用数总共有2n-1个叶节点。
钢条切割问题的动态规划求解
对每个子问题只求解一次，并将结果保存下来。不必重新计算。介绍两种方法
(1)带备忘的自顶向下法
按照递归的形式编写，使得子问题的求解只依赖于更小的子问题的解。当需要子问题的解的时候，只需要检查是否已经保存过值。如果已经保存过，就直接使用，否则按照通常的方式计算解。
下面给出算法的伪代码
这里实现算法(Java)
1 static int UpDown(int num, int[] arr) { 2 if(num == 0) return 0; 3 if(result[num] != 0) return result[num]; 4 5 int temp = 0; 6 for (int i = 1; i < num+1; i++) { 7 int max = arr[i] + UpDown(num-i, arr); 8 if(max > temp) { 9 temp = max; 10 } 11 } 12 result[num] = temp; //将计算的长度为n的钢条切割的长度用数组保存起来 13 return temp; 14 }
带备忘的自顶向下法
(2)自底向上方法
这种方法一般需要恰当的定义子问题的规模，使得每个子问题的求解只是依赖于更小的子问题，所以可以将子问题按照规模排序，按照由小到大的顺序排序。当求解某个子问题的时候，所依赖的那些更小的子问题都已经求解完毕，结果保存了。所以每个子问题只是求解一次。所依赖的前提子问题已经求解完成
给出算法的伪代码
给出算法的具体实现(Java)
1 static int DownUp(int num, int[] arr) { 2 for (int i = 1; i < num + 1; i++) { 3 int temp = 0; 4 for (int j = 1; j <= i; j++) { 5 int max = arr[j] + result[i - j]; 6 if(max > temp) { 7 temp = max; 8 } 9 } 10 result[i] = temp; 11 } 12 return result[num]; 13 }
自底向上法（bottom-up method）
Java实现两种方法
1 package cn.dp; 2 3 4 /** 5 * 动态规划实现实现钢条切割问题 6 * 7 */ 8 public class Test1 { 9 10 static int[] result = {0,0,0,0,0,0,0,0,0,0,0}; 11 static int[] s = {0,0,0,0,0,0,0,0,0,0,0}; 12 13 public static void main(String[] args) { 14 int[] arr = {0,1,5,8,9,10,17,17,20,24,30}; 15 /* 16 System.out.println("自顶向下结果"); 17 for (int i = 0; i < arr.length; i++) { 18 System.out.print("r"+ i +"=" + UpDown(i, arr)+"; "); 19 } 20 */ 21 /* 22 System.out.println("自底向上结果"); 23 for (int i = 0; i < arr.length; i++) { 24 System.out.print("r"+ i +"=" + DownUp(i, arr)+"; "); 25 } 26 */ 27 } 28 29 /** 30 * 自顶向下实现 31 */ 32 static int UpDown(int num, int[] arr) { 33 if(num == 0) return 0; 34 if(result[num] != 0) return result[num]; 35 36 int temp = 0; 37 for (int i = 1; i < num+1; i++) { 38 int max = arr[i] + UpDown(num-i, arr); 39 if(max > temp) { 40 temp = max; 41 } 42 } 43 result[num] = temp; //将计算的长度为n的钢条切割的长度用数组保存起来 44 return temp; 45 } 46 47 /** 48 * 自底向上实现 49 */ 50 static int DownUp(int num, int[] arr) { 51 for (int i = 1; i < num + 1; i++) { 52 int temp = 0; 53 for (int j = 1; j <= i; j++) { 54 int max = arr[j] + result[i - j]; 55 if(max > temp) { 56 temp = max; 57 } 58 } 59 result[i] = temp; 60 } 61 return result[num]; 62 } 63 64 /** 65 * 打印切割方案 66 */ 67 static int DownUpPrint(int num, int[] arr) { 68 for (int i = 1; i < num +1; i++) { 69 int temp = 0; 70 for (int j = 1; j <= i; j++) { 71 int max = arr[j] + result[i - j]; 72 if(max > temp) { 73 temp = max; 74 } 75 s[i] = j; 76 } 77 result[i] = temp; 78 } 79 return result[num]; 80 } 81 }
动态规划实现钢条切割问题