动态规划 -- 活动时间问题

活动时间问题描述：

有n个需要在同一天使用同一个教室的活动a1,a2,…,an，教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行（最大兼容活动子集）。

动态规划法代码实现：

using System;

namespace _4_3_1动态规划_活动选择问题_自底向上
{ class Program { static void Main(string[] args) { //活动开始时间s，结束时间f int[] s = { 0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12, 24 }; int[] f = { 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 24 }; //13是活动个数 List<int>[,] resultList = new List<int>[13, 13]; //初始值设空的集合 for (int a = 0; a < 13; a++) { for (int b = 0; b < 13; b++) { resultList[a, b] = new List<int>(); } } for (int j = 0; j < 13; j++) //j=2 时内层循环才会执行 { for (int i = 0; i < j - 1; i++) { //S(ij) i结束之后j开始之前的活动集合 //f[i] s[j] 这个时间区间内的所有活动 List<int> sij = new List<int>(); for (int k = 1; k < s.Length-1; k++) { if (s[k] >= f[i] && f[k] <= s[j]) { sij.Add(k); } } if (sij.Count > 0) { //result[i,j] = max{result[i,k]+result[k,j]+1} int maxCount = 0; //用于保存ij之间的最大活动时间 List<int> tempList = new List<int>(); foreach (int k in sij) { int count = resultList[i, k].Count + resultList[k, j].Count + 1; if (maxCount < count) { maxCount = count; //Union()用于合并量List tempList = resultList[i, k].Union<int>(resultList[k, j]).ToList(); tempList.Add(k); } } resultList[i, j] = tempList; } } } List<int> temp = resultList[0, 12]; foreach (int item in resultList[0, 12]) { Console.WriteLine(item); } //此代码运行结果是1 4 8 11 Console.ReadKey(); } }
}

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
 

文章来源: czhenya.blog.csdn.net，作者：陈言必行，版权归原作者所有，如需转载，请联系作者。

原文链接：czhenya.blog.csdn.net/article/details/78976022