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