동적 기획의 일련의 문제를 깊이 이해하다(14)

   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: }