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.HashMap;
19: import java.util.Map;
20:
21: public class ALLOT { 22:
23: private static int N = 3;
24: private static int M = 4;
25:
26: private static final double INF=Double.MAX_VALUE;
27:
28: private static Map<Integer,Integer> choices = new HashMap<Integer,Integer>();
29:
30: private static final double [][] c = { 31: {INF,1.0,0.8,0.4,0.0}, 32: {INF,1.0,0.5,0.0,0.0}, 33: {INF,1.0,0.6,0.3,0.0} 34: };
35:
36: private static double cost(int k, int d) { 37: return c[k-1][d];
38: }
39:
40: public static double f(int k, int m){ 41: if(k>N&&m>=0) return 0.0;
42: else{ 43: double mm = Double.MAX_VALUE;
44: int dispatch = -1;
45: for(int d=0;d<=m;d++){ 46: double t = cost(k,d)+f(k+1,m-d);
47: if(t<mm) { 48: mm = t;
49: dispatch = d;
50: }
51: }
52: if(!choices.containsKey(k))
53: choices.put(k, Integer.MAX_VALUE);
54: if(mm<choices.get(k))
55: choices.put(k,dispatch);
56: return mm;
57: }
58: }
59: /**
60: * @param args
61: */
62: public static void main(String[] args) { 63: double minCost = f(1,M);
64: System.out.println("min cost is : "+minCost); 65: System.out.print("solution is : "); 66: for(int i=1;i<=N;i++){ 67: System.out.print(choices.get(i));
68: if(i<N)
69: System.out.print(","); 70: }
71: }
72:
73: }