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.HashSet;
19: import java.util.Set;
20:
21: //IntegerLinearProgramming;
22: public class ILP { 23: // objective function coefficients
24: private static int[] c = { 3, 5 }; 25: // right hand side of constraints vector
26: private static int[] b = { 4, 12, 18 }; 27: // constraint matrix
28: private static int[][] a = { { 1, 0 }, { 0, 2 }, { 3, 2 } }; 29: private static int n = c.length;
30: private static int m = b.length;
31: private static final int infty = Integer.MAX_VALUE;
32:
33: private static Set<Integer> calculateDecisionSet(int stage, int y1, int y2,
34: int y3) { 35: Set<Integer> result = new HashSet<Integer>();
36: // maxPossibleChoiceBecauseOfResourceiRestriction, i=1,2,3
37: int mpc1 = infty;
38: int mpc2 = infty;
39: int mpc3 = infty;
40: if (a[0][stage] != 0) { 41: mpc1 = y1 / a[0][stage];
42: }
43: if (a[1][stage] != 0) { 44: mpc2 = y2 / a[1][stage];
45: }
46: if (a[2][stage] != 0) { 47: mpc3 = y3 / a[2][stage];
48: }
49: for (int i = 0; i <= Math.min(mpc1, Math.min(mpc2, mpc3)); i++) { 50: result.add(new Integer(i));
51: }
52: return result;
53: }
54:
55: // here: yi denotes how much of resource i is still available,
56: // (in other words how much slack is still available)
57: public static double f(int stage, int y1, int y2, int y3) { 58: if (stage == n) { 59: return 0.0;
60: }
61: double max = Double.MIN_VALUE;
62: for (int d : calculateDecisionSet(stage, y1, y2, y3)) { 63: double t = c[stage]
64: * d
65: + f(stage + 1, y1 - a[0][stage] * d, y2 - a[1][stage] * d,
66: y3 - a[2][stage] * d);
67: if (t > max)
68: max = t;
69: }
70: return max;
71: }
72:
73: /**
74: * @param args
75: */
76: public static void main(String[] args) { 77: System.out.println(ILP.f(0, b[0], b[1], b[2]));
78: }
79:
80: }