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: //optimal COVering problem
19: public class COV { 20: // cost of cover sizes 0,1,..,9 in dollar
21: private static int[] cost = { 1, 4, 5, 7, 8, 12, 13, 18, 19, 21 }; 22:
23: public static double f(int numberOfCoverSizes, int largestSize) { 24: //numberOfCoverSizes denotes the stage number in this problem
25: if (numberOfCoverSizes == 1)
26: return (largestSize + 1) * cost[largestSize];
27: double min = Double.MAX_VALUE;
28: for (int nextCoverSize = numberOfCoverSizes - 2; nextCoverSize <= largestSize - 1; nextCoverSize++) { 29: double t = (largestSize - nextCoverSize) * cost[largestSize]
30: + f(numberOfCoverSizes - 1, nextCoverSize);
31: if (t < min)
32: min = t;
33: }
34: return min;
35: }
36:
37: /**
38: * @param args
39: */
40: public static void main(String[] args) { 41: System.out.println(f(3, 9));
42: }
43:
44: }