动态规划实现钢条切割问题(Java)

动态规划算法的步骤
  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 }

动态规划实现钢条切割问题