1: /*
2: * Copyright (C) 2013 changedi
3: *
4: * Licensed under the Apache License, Version 2.0 (the "License");
5: * you may not use this file except in compliance with the License.
6: * You may obtain a copy of the License at
7: *
8: * http://www.apache.org/licenses/LICENSE-2.0
9: *
10: * Unless required by applicable law or agreed to in writing, software
11: * distributed under the License is distributed on an "AS IS" BASIS,
12: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13: * See the License for the specific language governing permissions and
14: * limitations under the License.
15: */
16: package com.jybat.dp;
17:
18: import java.util.Arrays;
19:
20: public class ARC { 21:
22: private static double[] weight = { 2, 3, 1, 4 }; 23:
24: private static int N = weight.length - 1;
25:
26: private static double sum(int p, int q) { 27: double result = 0.0;
28: for (int k = p; k <= q; k++) { 29: result += weight[k];
30: }
31: return result;
32: }
33:
34: public static double f(int firstIndex, int lastIndex){ 35: if(firstIndex == lastIndex)
36: return 0.0;
37: double min = Double.MAX_VALUE;
38: for(int d=firstIndex;d<lastIndex;d++){ 39: double t = f(firstIndex,d) + f(d+1,lastIndex) + sum(firstIndex,lastIndex);
40: if(t<min)
41: min = t;
42: }
43: return min;
44: }
45:
46: /**
47: * @param args
48: */
49: public static void main(String[] args) { 50: Arrays.sort(weight);
51: System.out.println(f(0,N));
52: }
53:
54: }