Algorithm/Week1.py at main · yadi-li/Algorithm · GitHub

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#Algorithm: Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
#Week 1
#Greedy algorithm

#Problem 1
#schedule jobs in decreasing order of the difference (weight - length)

#read the data
file = open("D:\\algorithm dataset\\jobs.txt", "r")
data = file.readlines()

#10000 jobs
jobs=[[] for i in range(10000)]
i=0
for line in data[1:]:
	items=line.split()
	#weight of each job
	jobs[i].append(int(items[0]))
	#length of each job
	jobs[i].append(int(items[1]))
	#difference (weight-length) of each job
	jobs[i].append(jobs[i][0]-jobs[i][1])
	i+=1

#order the jobs by decreasing order of difference
#if two jobs have equal difference, schedule the job with higher weight first
order=sorted(range(len(jobs)),key=lambda k: (jobs[k][2], jobs[k][0]),reverse=True)


completion_time=[]
ordered_weight=[]
c=0
weighted_sum=0
#in the order of jobs in the schedule
for i in range(10000):
	length=jobs[order[i]][1]
	c+=length
	completion_time.append(c)
	ordered_weight.append(jobs[order[i]][0])
	weighted_sum+=completion_time[i]*ordered_weight[i]


#print(weighted_sum)
#answer: 69119377652


####################
#Problem 2
#schedule jobs in decreasing order of the ratio (weight/length)


#10000 jobs
jobs2=[[] for i in range(10000)]
i=0
for line in data[1:]:
	items=line.split()
	#weight of each job
	jobs2[i].append(int(items[0]))
	#length of each job
	jobs2[i].append(int(items[1]))
	#ratio (weight/length) of each job
	jobs2[i].append(jobs2[i][0]/jobs2[i][1])
	i+=1

#order the jobs by decreasing order of ratio
order2=sorted(range(len(jobs2)),key=lambda k: (jobs2[k][2]),reverse=True)


completion_time2=[]
ordered_weight2=[]
c2=0
weighted_sum2=0
#in the order of jobs in the schedule
for i in range(10000):
	length=jobs[order2[i]][1]
	c2+=length
	completion_time2.append(c2)
	ordered_weight2.append(jobs2[order2[i]][0])
	weighted_sum2+=completion_time2[i]*ordered_weight2[i]


#print(weighted_sum2)
#answer: 67311454237


#Problem 3
#Prim's minimum spanning tree

#read the data
file = open("D:\\algorithm dataset\\edges.txt", "r")
data = file.readlines()

graph={}
for line in data[1:]:
	items=line.split()
	if int(items[0]) not in graph:
		graph[int(items[0])]={}
	#for each start_node, initialize a dictionary to store the edge cost
	graph[int(items[0])][int(items[1])]=int(items[2])

	#another direction
	if int(items[1]) not in graph:
		graph[int(items[1])]={}
	graph[int(items[1])][int(items[0])]=int(items[2])


#initialize the first node (randomly choose one node)
#X stores the nodes that have already been spanned
X=[1]
cost=0

#number of nodes in the graph: 500
while len(X)<500:
	min_cost=float('inf')
	next_node=0
	for start_node in X:
		#for each edge of each node in X
		for end_node in graph[start_node].keys():
			#if it is a cross edge, keep track of the minimum edge cost
			if end_node not in X and graph[start_node][end_node]<min_cost:
				min_cost=graph[start_node][end_node]
				next_node=end_node
	#append the node into X
	X.append(next_node)
	#accumulate the cost of MST
	cost+=min_cost

print(cost)
#answer: -3612829