1: package com.jybat.dp;
2:
3: import java.util.Set;
4: import java.util.SortedSet;
5: import java.util.TreeSet;
6:
7: //deadline scheduling of unit-time jobs
8: public class DEADLINE { 9:
10: private static int[] profit = { 10, 15, 20, 1, 5 }; 11: private static int[] deadline = { 1, 2, 2, 3, 3 }; // sorted 12: private static int N = profit.length; // no.of jobs
13:
14: private static SortedSet<Integer> setOfAllJobs = new TreeSet<Integer>();
15:
16: public DEADLINE() { 17: for (int i = 0; i < N; i++) { 18: setOfAllJobs.add(i);
19: }
20: }
21:
22: private static boolean feasible(SortedSet<Integer> jobs, int k, int d) { 23: int j = 0;
24: for (int i = 0; i < N; i++) { 25: if (!(jobs.contains(new Integer(i))) || i == d) { 26: // if i already chosen or next (and is j-th),
27: // does it meet its deadline?
28: if (deadline[i] < ++j) { 29: return false;
30: }
31: }
32: }
33: return true;
34: }
35:
36: private static int cost(SortedSet<Integer> jobs, int k, int d) { 37: if (feasible(jobs, k, d)) { 38: return profit[d];
39: } else { 40: return 0;
41: }
42: }
43:
44: // jobs not yet chosen at stage k
45: public int f(SortedSet<Integer> jobs, int k) { 46: if (k > N)
47: return 0;
48: int max = Integer.MIN_VALUE;
49: for (int d : jobs) { 50: SortedSet<Integer> nJobs = copySet(jobs);
51: nJobs.remove(d);
52: int t = cost(jobs, k, d) + f(nJobs, k + 1);
53: if (t > max)
54: max = t;
55: }
56: return max;
57: }
58:
59: private SortedSet<Integer> copySet(SortedSet<Integer> jobs) { 60: SortedSet<Integer> nJobs = new TreeSet<Integer>();
61: for (int i : jobs) { 62: nJobs.add(i);
63: }
64: return nJobs;
65: }
66:
67: /**
68: * @param args
69: */
70: public static void main(String[] args) { 71: DEADLINE d = new DEADLINE();
72: System.out.println(d.f(setOfAllJobs, 1));
73: }
74:
75: }