最优钢条切割

2018-06-18 02:22:25来源：未知阅读 ()

自底向上方法：

 1 public class tmp {
 2 
 3     private static int r[];
 4 
 5     private static int BOTTON_UP_CUT_ROD(int n, int p[]) {
 6         r[0] = 0;// r[0]表示长度为0的时候的收益
 7         int i;
 8         for (i = 1; i <= n; i++) {
 9             // i表示在限定长度范围内的变化
10             int max = -9999;
11             for (int j = 1; j <= i; j++) {
12                 // j表示当前需要的长度，
13                 // r[i-j]+p[j]则表示在当前选择长度的情况下的利润p[j]以及更小子问题的最优解（前边长度的最优利润）之和
14                 max = (r[i - j] + p[j]) > max ? (r[i - j] + p[j]) : max;
15             }
16             r[i] = max;
17         }
18         return r[i - 1];
19     }
20 
21     /*
22      * p[]利润，r[]收益,length钢条长度
23      */
24     public static void main(String[] args) {
25         while (true) {
26             Scanner sc = new Scanner(System.in);
27             int num = sc.nextInt();
28             int p[] = new int[num + 1];
29             p[0] = 0;
30             for (int i = 1; i <= num; i++)
31                 p[i] = sc.nextInt();
32             int length = sc.nextInt();
33             r = new int[length + 1];
34             System.out.println(BOTTON_UP_CUT_ROD(length, p));
35         }
36     }
37 }

带备忘的自顶向下法：

 1 public class tmp {
 2 
 3     private static int r[];
 4 
 5     private static int MEMOIZED_CUT_ROD_AUX(int n, int p[]) {
 6         if (r[n] >= 0)
 7             return r[n];
 8         int max = -999;
 9         for (int j = 1; j <= n; j++) {
10             int t = MEMOIZED_CUT_ROD_AUX(n - j, p) + p[j];
11             
12             max = max > t ? max : t;
13         }
14         return max;
15     }
16 
17     public static int MEMOIZED_CUT_ROD(int n, int p[]) {
18         r[0] = 0;
19         for (int i = 1; i <= n; i++)
20             r[i] = -99999;
21         for (int i = 1; i <= n; i++)
22             r[i] = MEMOIZED_CUT_ROD_AUX(i, p);
23         return r[n];
24     }
25 
26     /*
27      * p[]利润，r[]收益,length钢条长度
28      */
29     public static void main(String[] args) {
30         while (true) {
31             Scanner sc = new Scanner(System.in);
32             int num = sc.nextInt();
33             int p[] = new int[num + 1];
34             p[0] = 0;
35             for (int i = 1; i <= num; i++)
36                 p[i] = sc.nextInt();
37             int length = sc.nextInt();
38             r = new int[length + 1];
39             System.out.println(MEMOIZED_CUT_ROD(length, p));
40         }
41     }
42 }