活动选择问题

活动选择问题

无权值

问题背景

有一个会场,需要安排几场活动

  • 公司年会:10:00 - 19:00
  • 婚礼宴请:11:00- 14:00
  • 生日聚会:12:00 - 17:00
  • 学术研究:14:00 - 16:00

问 如果安排这个会场能让活动尽可能的多的进行?

有下面这几个活动和占比时间

选择出租的时间不能有冲突

image-20220509220835912

问题研究,策略选择

​ 这时候我们采用贪心策略:

  • 策略一:最短活动优先

    image-20220509221229806

  • 策略二:最早开始的活动优先

image-20220509221319145

  • 策略三:最早结束活动优先

选择最早结束的活动,可以给后面的活动留出更大的弓箭

  1. 证明该策略是正确的(替换法)

image-20220509221937188

我们可以通过替换的规则让 某个最优解替换为 贪心所得的最优解,在替换的时候,如果活动相同的话,直接替换即可,如果不相同的话,因为贪心所得的是这个活动的最先完成 的活动,所有会给后面的活动留出的活动空间更大不会影响后面活动的替换

代码实现

输入:活动集合S={a1, a2, a3 … an},每个活动ai的起始时间si 结束时间 fi

输出:不冲突的最大子集S‘

先把活动结束时间由小到大排个序

先给数组S赋值 a1(因为这里a1是最早活动的结束时间)

令K = 1

for i 循环 从2 到最后

如果 ai 的起始时间 小于 ak的结束时间的话,就把ai添加到S’中, 把 i赋值给k

最后返回 S

image-20220509223210781

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
import random

# 活动选择问题
# 我们是用元组来初始化数据(开始时间, 结束时间)

# 按照活动结束时间从小到大排序


def activity_sort(data):
# data中的数据都是按照活动结束时间从小到大排序的,也就是说a1是结束时间最早的,依次排序
S = []
S.append(data[0])
print("事件1")

k = 0
for i in range(1, len(data)):
# 如果第i个时间的开始时间 小于第k个时间的结束时间的话,则表明这个时间他冲突,跳过
if data[i][0] >= data[k][1]:
print(f"事件{i+1}")
k = i
return S


# 快速排序
def quick_sort(data, start, end):

if start > end:
return 0

# 先获取一个随机数当做主元
prime_index = random.randint(start, end)

# 把这个随机数放到最后方便计算
data[end], data[prime_index] = data[prime_index], data[end]

# 寻找该主元的正确的下标
# 下标i以后的为小于主元元素的
# 下标j以后i以前的表示大于该元素的

i = start-1
j = start

while j < end:
# 如果j 元素比主元小的话,就让i+1元素和j元素互换位置,并让i+=1 j+=1
# 因为:下标i以后的为小于主元元素的,下标j以后i以前的表示大于该元素的
if data[j][1] <= data[end][1]:
data[i+1], data[j] = data[j], data[i+1]
i += 1
j += 1
else:
j += 1

# 最后吧主元放到对应的位置
data[i+1], data[end] = data[end], data[i+1]

# 进行递归调用
quick_sort(data, start, i)
quick_sort(data, i+2, end)

data = [(1,4,1),(0,6,4), (3,5,6),(2,14,8), (3,9,3), (4,7,7),(5,9,12), (6,10,2), (8,11,9),(8,12,11)]
quick_sort(data, 0, 9)
activity_sort(data)

有权值

上述问题我们默认为每个事件的收入都是 1, 所以我们关注一共有多少个时间的发生:

所以相比于上面的问题我们多了一个权重:

image-20220509223538140

这时候如果我们在向上面的方式来进行选择问题的话,这时候可能就会得不偿失

image-20220509223656332

如果按照上述方法进行第一个问题的话 我们选择的权值和为2 , 但是实际上我们想要的权值和为 10000

问题分析

image-20220509224200970

这时候我们需要进行动态规划 + 贪心算法来求解这个问题, 选择a6 和 a5的时候我们可以根据前面的最优问题来进行求解

问题预处理

这里我们需要定义一个

p数组 p[i] 表示在a[i]开始前最后结束的活动,

p数组目的:为了防止活动冲突

D[i]数组:集合{a1, a2, a3… an}中不冲突活动的最大权值和

递推关系建立

当我们在ai的时候,

  1. 选择ai 那么 D[i] = Wai + D[p[i]]
  2. 不选择ai D[i] = D[i-1]
  3. 递推公式:D[i] = max{D[pi] + w, D[i-1]}

计算过程

P数组表示 ai 发生之前的最晚发生的事件

D数组表示权值的最大

Rec 1表示选择这个活动, 0表示不选择这个活动

image-20220509225814085

代码实现

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
import random

# 活动选择问题
# 我们是用元组来初始化数据(开始时间, 结束时间)

# 按照活动结束时间从小到大排序


def activity_sort(data, D, Rec, p):

# 进行D数组和Rec数组
# D数组:权值选择问题
# Rec数组:是否选择改事件
# D[i] 的依据是 max{D[i-1], D[p1] + wi}
for num_index in range(len(data)):
if D[num_index] > (D[p[num_index]] + data[num_index][2]):
D[num_index+1] = D[num_index]
Rec[num_index] = 0
else:
D[num_index+1] = D[p[num_index]] + data[num_index][2]
Rec[num_index] = 1

# 数组追踪
print(f"事件总权重为{D[len(D)-1]}")
i = len(Rec)-1
while i >= 0:
if Rec[i] == 1:
print(f"选择事件{i+1},权重{data[i][2]}")
i = p[i]-1
continue
i -= 1


# 快速排序
def quick_sort(data, start, end):

if start > end:
return 0

# 先获取一个随机数当做主元
prime_index = random.randint(start, end)

# 把这个随机数放到最后方便计算
data[end], data[prime_index] = data[prime_index], data[end]

# 寻找该主元的正确的下标
# 下标i以后的为小于主元元素的
# 下标j以后i以前的表示大于该元素的

i = start-1
j = start

while j < end:
# 如果j 元素比主元小的话,就让i+1元素和j元素互换位置,并让i+=1 j+=1
# 因为:下标i以后的为小于主元元素的,下标j以后i以前的表示大于该元素的
if data[j][1] <= data[end][1]:
data[i+1], data[j] = data[j], data[i+1]
i += 1
j += 1
else:
j += 1

# 最后吧主元放到对应的位置
data[i+1], data[end] = data[end], data[i+1]

# 进行递归调用
quick_sort(data, start, i)
quick_sort(data, i+2, end)

# 初始化p数组
def init_p(data):
p = [0 for i in range(len(data))]

for i in range(len(data)):
# k表示第i个时间的起始时间
start_time = data[i][0]
start = 0
end = len(data)-1
flag = 0
while(start < end):
mid = start + int((end - start)/2)
# 如果中间事件的结束时间小于要查找的事件
if data[mid][1] == start_time:
flag = mid
break
elif data[mid][1] > start_time:
end = mid-1
else:
start = mid + 1
if flag != 0:
p[i] = flag+1
elif data[start][1] > start_time:
p[i] = start
else:
p[i] = start+1
return p



data = [(1,4,1),(0,6,4), (3,5,6),(2,14,8), (3,9,3), (4,7,7),(5,9,12), (6,10,2), (8,11,9),(8,12,11)]
quick_sort(data, 0, 9)

D = [0 for i in range(len(data) + 1)]
Rec = [0 for i in range(len(data))]
# 初始化P数组 p[i] 表示事件i开始前最晚结束的事件
p = init_p(data)

activity_sort(data, D, Rec, p)
print(D)
print(Rec)
print(p)