Change Dir

• 随笔 - 222
• 文章 - 0
• 评论 - 182
• 引用 - 0

• 积分 - 417659
• 排名 - 133

深入理解动态规划的一系列问题（13）

   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: //Flowshop Problem
  22: public class FLOWSHOP {
  23:
  24:     private static int[] first = { 3, 4, 8, 10 }; // sum=25
  25:     private static int[] second = { 6, 2, 9, 15 }; // sum=32
  26:     // upper bound on final completion time is 25+32:
  27:     private static int sum = 57;
  28:     private static int m = first.length;
  29:
  30:     private static Set<Integer> setOfAllItems = new HashSet<Integer>();
  31:
  32:     static{
  33:         setOfAllItems.add(0);
  34:         setOfAllItems.add(1);
  35:         setOfAllItems.add(2);
  36:         setOfAllItems.add(3);
  37:     }
  38:
  39:     private static int fct(int t, int d) {
  40:         return Math.max(t - first[d], 0) + second[d];
  41:     }
  42:
  43:     public static double f(Set<Integer> set, int t){
  44:         if(set.isEmpty())
  45:             return t;
  46:         double min = Double.MAX_VALUE;
  47:         for(int d : set){
  48:             Set<Integer> tmpSet = copySet(set);
  49:             tmpSet.remove(d);
  50:             double tmp = first[d]+f(tmpSet,fct(t,d));
  51:             if(tmp<min){
  52:                 min=tmp;
  53:             }
  54:         }
  55:         return min;
  56:     }
  57:
  58:     private static Set<Integer> copySet(Set<Integer> set) {
  59:         Set<Integer> s = new HashSet<Integer>();
  60:         for(int x : set){
  61:             s.add(x);
  62:         }
  63:         return s;
  64:     }
  65:
  66:     /**
  67:      * @param args
  68:      */
  69:     public static void main(String[] args) {
  70:         System.out.println(f(setOfAllItems,0));
  71:     }
  72:
  73: }

posted on 2014-06-03 19:24 changedi 阅读(1513) 评论(0)  编辑  收藏 所属分类: 算法

 只有注册用户登录后才能发表评论。 网站导航: 相关文章: