# Change Dir

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

• 积分 - 417192
• 排名 - 133

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

   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: /**
  22:  * Knapsack01Problem.
  23:  *
  24:  * @author zunyuan.jy
  25:  *
  26:  * @since 2014年6月13日
  27:  */
  28: public class KS01 {
  29:
  30:     private static int knapsackCapacity = 22;
  31:     private static int[] value = { 25, 24, 15 };
  32:     private static int[] weight = { 18, 15, 10 };
  33:     private static int n = value.length; // number of objects n=3
  34:     private static int highestIndex = n - 1; // items are indexed
  35:
  36:     // from 0 through n-1
  37:
  38:     private static Set<Integer> calculateDecisionSet(int objInd, int w) {
  39:         Set<Integer> decSet = new HashSet<Integer>();
  40:         decSet.add(new Integer(0)); // decision to not take object
  41:         // is always feasible
  42:         if (w >= weight[objInd]) { // check if there is enough space
  43:             // to take object
  44:             decSet.add(new Integer(1));
  45:         }
  46:         return decSet;
  47:     }
  48:
  49:     public static double f(int currentObejctIndex, int weightToGive) {
  50:         if (currentObejctIndex == -1)
  51:             return 0.0;
  52:         Set<Integer> decisionSet = calculateDecisionSet(currentObejctIndex,
  53:                 weightToGive);
  54:         double max = 0.0;
  55:         for (int d : decisionSet) {
  56:             double tmp = d
  57:                     * value[currentObejctIndex]
  58:                     + f(currentObejctIndex - 1, weightToGive - d
  59:                             * weight[currentObejctIndex]);
  60:             if (tmp > max)
  61:                 max = tmp;
  62:         }
  63:         return max;
  64:     }
  65:
  66:     /**
  67:      * @param args
  68:      */
  69:     public static void main(String[] args) {
  70:         System.out.println(KS01.f(2, 22));
  71:     }
  72:
  73: }

posted on 2014-06-16 13:02 changedi 阅读(2470) 评论(6)  编辑  收藏 所属分类: 算法

### 评论

#### #re: 深入理解动态规划的一系列问题（15） 2014-06-16 14:25 IT前线

http://www.itqx.net  回复  更多评论

#### #re: 深入理解动态规划的一系列问题（15） 2014-07-15 02:29 自媒体

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