-
Notifications
You must be signed in to change notification settings - Fork 66
/
activity_selection.py
101 lines (85 loc) · 3 KB
/
activity_selection.py
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
from numpy import zeros
def activity_selection(s, f, n):
c = zeros((n + 2, n + 2))
activities = zeros((n + 2, n + 2))
s = [float("-Inf")] + s[0:n] + [float("Inf")]
f = [float("-Inf")] + f[0:n] + [float("Inf")]
for l in range(3, n + 3):
for i in range(n + 3 - l):
j = i + l - 1
print("i = {}, j = {}".format(i, j))
for k in range(i + 1, j):
print("k = {}".format(k))
print("s[{}] = {}, f[{}] = {}".format(k, s[k], k, f[k]))
print("s[{}] = {}, f[{}] = {}".format(j, s[j], i, f[i]))
if f[i] <= s[k] and f[k] <= s[j]:
t = c[i, k] + c[k, j] + 1
print("t = {}, c[{}, {}] = {}".format(t, i, j, c[i, j]))
if t > c[i, j]:
c[i, j] = t
activities[i, j] = k
return c, activities
def activity_selection_with_weight(s, f, v, n):
"""
This is a modification to the activity-selection problem in which each activity has,
in addition to a start and finish time, a value v. Now the object is to maximize
the total value of the activities scheduled. It can be solved by dynamic programming method
"""
c = zeros((n + 2, n + 2))
activities = zeros((n + 2, n + 2))
s = [float("-Inf")] + s[0:n] + [float("Inf")]
f = [float("-Inf")] + f[0:n] + [float("Inf")]
for l in range(3, n + 3):
for i in range(n + 3 - l):
j = i + l - 1
for k in range(i + 1, j):
if f[i] <= s[k] and f[k] <= s[j]:
t = c[i, k] + c[k, j] + v[k - 1]
if t > c[i, j]:
c[i, j] = t
activities[i, j] = k
return c, activities
def recursive_activity_selector(s, f, n):
f = [float("-Inf")] + f
return recursive_activity_selector_aux(s, f, 0, n)
def recursive_activity_selector_aux(s, f, k, n):
m = k + 1
while m <= n and s[m - 1] < f[k]:
m = m + 1
if m <= n:
return {m}.union(recursive_activity_selector_aux(s, f, m, n))
else:
return {}
def greedy_activity_selector(s, f):
n = len(s)
A = {1}
k = 1
for m in range(2, n + 1):
if s[m - 1] >= f[k - 1]:
A = A.union({m})
k = m
return A
def greedy_activity_selector_last(s, f):
"""Instead of always selecting the first activity to finish,
select the last activity to start that is compatible with all
previously selected activities
"""
n = len(s)
A = {n}
k = n
for m in range(n - 1, 0, -1):
if f[m - 1] <= s[k - 1]:
A = A.union({m})
k = m
return A
def print_activity(activities):
m = activities.shape[0] - 1
n = activities.shape[1] - 1
print_activity_aux(activities, 0, n)
def print_activity_aux(activities, m, n):
a = activities[m, n]
if a == 0:
return
print_activity_aux(activities, m, a)
print(int(a))
print_activity_aux(activities, a, n)