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: public class ASMBAL { 19:
20: private static int[][] cost = // (stage,line)
21: { 22: { 2, 4 }, // to next line 23: { 2, 2 }, { 1, 3 }, { 2, 1 }, { 2, 3 }, { 1, 4 }, // to next line 24: { 3, 2 } // from line 25: };
26: private static int[][] vertexcost = // (stage,line)
27: { 28: { 0, 0 }, { 7, 8 }, { 9, 5 }, { 3, 6 }, { 4, 4 }, { 8, 5 }, { 4, 7 } 29: };
30: private static int N = vertexcost.length - 1;
31:
32: private static int arccost(int g, int x, int d) { 33: if (g == 0)
34: return cost[g][d]; // to next line d
35: else if (g == N)
36: return cost[g][x]; // from line x
37: else if (x == d)
38: return 0; // stay same line
39: else
40: return cost[g][d]; // to next line d
41: }
42:
43: public static double f(int g, int x) { 44: if (g > N)
45: return 0.0;
46: double min = Double.MAX_VALUE;
47: for (int d = 0; d <= 1; d++) { 48: double c = vertexcost[g][x] + arccost(g, x, d) + f(g + 1, d);
49: if (c < min)
50: min = c;
51: }
52: return min;
53: }
54: /**
55: * @param args
56: */
57: public static void main(String[] args) { 58: System.out.println(f(0,0));
59: }
60:
61: }