活动选择问题

活动选择问题

无权值

问题背景

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

  • 公司年会：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)

​