# Change Dir

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

• 积分 - 416920
• 排名 - 133

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

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

posted on 2014-05-12 16:54 changedi 阅读(2635) 评论(1)  编辑  收藏 所属分类: 算法

### 评论

#### #re: 深入理解动态规划的一系列问题（10） 2014-05-12 23:45 ME娱乐澳门银座时时彩平台

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