FilesExpand file tree

 master

/

activity_selection.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

83 lines (82 loc) · 2.96 KB

 master

/

activity_selection.py

Copy path

Top

File metadata and controls

• Code
• Blame

83 lines (82 loc) · 2.96 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

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(0, 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 activies 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(0, 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)