Final Project: CFLP

Posted on | Edited on | Comments: | Views:
Greedy; SA

问题描述:

Suppose there are n facilities and m customers. We wish to choose:
(1) which of the n facilities to open
(2) the assignment of customers to facilities
(3) The objective is to minimize the sum of the opening cost and the assignment cost.
(4) The total demand assigned to a facility must not exceed its capacity.

简单地说就是我们要选择一些 设施 来服务 顾客, 使得 总成本 最小

贪心算法:

首先说明一下, (本文的)贪心算法在此问题只能求一个近似解, 究其原因是只考虑了简单的一个因素(顾客成本), 而没有考虑全局(设施成本等)的相互影响

从问题和数据来看, 顾客方面花费的成本要 远远大于 设施的开启成本, 一个设施开启与否的成本和一个安排成本相比, 几乎可以忽略不记, 所以可以简单地考虑较好地安排好顾客以 降低主要成本 来求得近似最优解

贪心策略:
  1. 对于一个顾客, 首先要尽量安排到成本最低的设施;
  2. 对于全体顾客, 首先安排成本增长很快的顾客;
策略的解释:

对于 1, 很容易理解, 就是降低成本;
对于 2, 就是考虑到某些顾客成本增长十分迅速, 越后安排成本越高, 所以考虑提前安排到成本较低的设施去;

结果:
序号 成本 时间 序号 成本 时间 序号 成本 时间
01 9307 0.000 20 17180 0.000 39 21389 0.003
02 7993 0.000 21 12032 0.001 40 26789 0.002
03 9993 0.000 22 9180 0.000 41 7107 0.001
04 11993 0.000 23 13180 0.000 42 9957 0.001
05 9220 0.000 24 17180 0.000 43 12448 0.001
06 7906 0.000 25 19071 0.000 44 7215 0.000
07 9906 0.000 26 16005 0.002 45 9848 0.001
08 11906 0.000 27 21405 0.002 46 12639 0.001
09 9040 0.000 28 26805 0.003 47 6593 0.001
10 7726 0.000 29 19056 0.003 48 9044 0.001
11 9726 0.000 30 15990 0.004 49 12420 0.001
12 11726 0.001 31 21390 0.003 50 9848 0.001
13 12032 0.001 32 26790 0.003 51 11340 0.001
14 9180 0.000 33 19055 0.004 52 10388 0.000
15 13180 0.000 34 15989 0.003 53 12432 0.001
16 17180 0.001 35 21389 0.004 54 9556 0.001
17 12032 0.001 36 26789 0.003 55 11889 0.001
18 9180 0.001 37 19055 0.003 56 23882 0.004
19 13180 0.000 38 15989 0.002 57 32882 0.004
58 53882 0.004 63 39121 0.004 68 23882 0.006
59 39121 0.004 64 23882 0.005 69 32882 0.005
60 23882 0.006 65 32882 0.004 70 53882 0.004
61 32882 0.005 66 53882 0.007 71 39121 0.005
62 53882 0.005 67 39671 0.008
分配方法:
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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355

p1:
9307
1 1 1 1 1 1 1 1 1 1 
8 2 1 6 3 8 2 4 4 1 9 8 3 2 0 3 4 0 9 7 3 4 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 0 4 1 8 1 5 7 0 4 0 4 0 

p2:
7993
1 1 1 1 1 1 1 1 1 1 
8 2 1 6 3 8 2 4 4 1 9 8 3 2 0 3 4 0 9 7 3 4 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 0 4 1 8 1 5 7 0 4 0 4 0 

p3:
9993
1 1 1 1 1 1 1 1 1 1 
8 2 1 6 3 8 2 4 4 1 9 8 3 2 0 3 4 0 9 7 3 4 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 0 4 1 8 1 5 7 0 4 0 4 0 

p4:
11993
1 1 1 1 1 1 1 1 1 1 
8 2 1 6 3 8 2 4 4 1 9 8 3 2 0 3 4 0 9 7 3 4 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 0 4 1 8 1 5 7 0 4 0 4 0 

p5:
9220
1 1 1 1 1 1 1 1 1 1 
8 8 1 6 3 8 2 4 4 1 9 8 3 2 8 3 4 0 9 7 3 7 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 8 4 1 8 1 5 7 0 2 0 7 0 

p6:
7906
1 1 1 1 1 1 1 1 1 1 
8 8 1 6 3 8 2 4 4 1 9 8 3 2 8 3 4 0 9 7 3 7 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 8 4 1 8 1 5 7 0 2 0 7 0 

p7:
9906
1 1 1 1 1 1 1 1 1 1 
8 8 1 6 3 8 2 4 4 1 9 8 3 2 8 3 4 0 9 7 3 7 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 8 4 1 8 1 5 7 0 2 0 7 0 

p8:
11906
1 1 1 1 1 1 1 1 1 1 
8 8 1 6 3 8 2 4 4 1 9 8 3 2 8 3 4 0 9 7 3 7 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 8 4 1 8 1 5 7 0 2 0 7 0 

p9:
9040
1 1 1 1 1 1 1 1 1 1 
8 8 1 6 3 8 2 4 4 1 9 8 3 2 8 3 4 0 9 7 3 8 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 0 4 1 8 1 5 7 0 4 0 4 0 

p10:
7726
1 1 1 1 1 1 1 1 1 1 
8 8 1 6 3 8 2 4 4 1 9 8 3 2 8 3 4 0 9 7 3 8 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 0 4 1 8 1 5 7 0 4 0 4 0 

p11:
9726
1 1 1 1 1 1 1 1 1 1 
8 8 1 6 3 8 2 4 4 1 9 8 3 2 8 3 4 0 9 7 3 8 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 0 4 1 8 1 5 7 0 4 0 4 0 

p12:
11726
1 1 1 1 1 1 1 1 1 1 
8 8 1 6 3 8 2 4 4 1 9 8 3 2 8 3 4 0 9 7 3 8 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 0 4 1 8 1 5 7 0 4 0 4 0 

p13:
12032
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
16 12 10 10 1 18 17 13 14 17 15 4 1 6 13 3 15 10 4 9 12 15 15 19 6 17 16 17 1 17 13 7 2 16 3 10 11 19 19 13 6 0 5 0 8 5 14 10 19 9 

p14:
9180
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
16 12 10 10 1 18 17 13 14 17 15 4 1 6 13 3 15 10 4 9 12 15 15 19 6 17 16 17 1 17 13 7 2 16 3 10 11 19 19 13 6 0 5 0 8 5 14 10 19 9 

p15:
13180
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
16 12 10 10 1 18 17 13 14 17 15 4 1 6 13 3 15 10 4 9 12 15 15 19 6 17 16 17 1 17 13 7 2 16 3 10 11 19 19 13 6 0 5 0 8 5 14 10 19 9 

p16:
17180
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
16 12 10 10 1 18 17 13 14 17 15 4 1 6 13 3 15 10 4 9 12 15 15 19 6 17 16 17 1 17 13 7 2 16 3 10 11 19 19 13 6 0 5 0 8 5 14 10 19 9 

p17:
12032
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
16 12 10 10 1 18 17 13 14 17 15 4 1 6 13 3 15 10 4 9 12 15 15 19 6 17 16 17 1 17 13 7 2 16 3 10 11 19 19 13 6 0 5 0 8 5 14 10 19 9 

p18:
9180
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
16 12 10 10 1 18 17 13 14 17 15 4 1 6 13 3 15 10 4 9 12 15 15 19 6 17 16 17 1 17 13 7 2 16 3 10 11 19 19 13 6 0 5 0 8 5 14 10 19 9 

p19:
13180
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
16 12 10 10 1 18 17 13 14 17 15 4 1 6 13 3 15 10 4 9 12 15 15 19 6 17 16 17 1 17 13 7 2 16 3 10 11 19 19 13 6 0 5 0 8 5 14 10 19 9 

p20:
17180
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
16 12 10 10 1 18 17 13 14 17 15 4 1 6 13 3 15 10 4 9 12 15 15 19 6 17 16 17 1 17 13 7 2 16 3 10 11 19 19 13 6 0 5 0 8 5 14 10 19 9 

p21:
12032
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
16 12 10 10 1 18 17 13 14 17 15 4 1 6 13 3 15 10 4 9 12 15 15 19 6 17 16 17 1 17 13 7 2 16 3 10 11 19 19 13 6 0 5 0 8 5 14 10 19 9 

p22:
9180
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
16 12 10 10 1 18 17 13 14 17 15 4 1 6 13 3 15 10 4 9 12 15 15 19 6 17 16 17 1 17 13 7 2 16 3 10 11 19 19 13 6 0 5 0 8 5 14 10 19 9 

p23:
13180
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
16 12 10 10 1 18 17 13 14 17 15 4 1 6 13 3 15 10 4 9 12 15 15 19 6 17 16 17 1 17 13 7 2 16 3 10 11 19 19 13 6 0 5 0 8 5 14 10 19 9 

p24:
17180
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
16 12 10 10 1 18 17 13 14 17 15 4 1 6 13 3 15 10 4 9 12 15 15 19 6 17 16 17 1 17 13 7 2 16 3 10 11 19 19 13 6 0 5 0 8 5 14 10 19 9 

p25:
19071
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 
20 11 13 2 20 5 2 9 14 17 22 16 8 20 3 14 14 17 5 11 2 0 5 3 5 8 19 24 5 24 5 25 6 25 20 20 24 15 0 14 0 14 15 8 24 14 0 13 27 8 29 14 14 5 13 20 17 11 0 14 0 5 20 11 11 11 9 0 5 9 20 6 11 17 24 8 26 20 14 24 20 7 13 17 19 17 17 4 20 5 2 24 17 11 7 5 2 2 21 16 8 7 17 25 2 29 7 11 14 28 14 1 2 11 11 21 24 24 24 24 5 8 25 13 16 0 5 9 0 12 0 11 24 5 8 14 7 5 20 17 0 8 20 14 8 25 25 5 2 5 

p26:
16005
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 
20 11 13 2 20 5 2 9 14 17 22 16 8 20 3 14 14 17 5 11 2 0 5 3 5 8 19 24 5 24 5 25 6 25 20 20 24 15 0 14 0 14 15 8 24 14 0 13 27 8 29 14 14 5 13 20 17 11 0 14 0 5 20 11 11 11 9 0 5 9 20 6 11 17 24 8 26 20 14 24 20 7 13 17 19 17 17 4 20 5 2 24 17 11 7 5 2 2 21 16 8 7 17 25 2 29 7 11 14 28 14 1 2 11 11 21 24 24 24 24 5 8 25 13 16 0 5 9 0 12 0 11 24 5 8 14 7 5 20 17 0 8 20 14 8 25 25 5 2 5 

p27:
21405
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 
20 11 13 2 20 5 2 9 14 17 22 16 8 20 3 14 14 17 5 11 2 0 5 3 5 8 19 24 5 24 5 25 6 25 20 20 24 15 0 14 0 14 15 8 24 14 0 13 27 8 29 14 14 5 13 20 17 11 0 14 0 5 20 11 11 11 9 0 5 9 20 6 11 17 24 8 26 20 14 24 20 7 13 17 19 17 17 4 20 5 2 24 17 11 7 5 2 2 21 16 8 7 17 25 2 29 7 11 14 28 14 1 2 11 11 21 24 24 24 24 5 8 25 13 16 0 5 9 0 12 0 11 24 5 8 14 7 5 20 17 0 8 20 14 8 25 25 5 2 5 

p28:
26805
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 
20 11 13 2 20 5 2 9 14 17 22 16 8 20 3 14 14 17 5 11 2 0 5 3 5 8 19 24 5 24 5 25 6 25 20 20 24 15 0 14 0 14 15 8 24 14 0 13 27 8 29 14 14 5 13 20 17 11 0 14 0 5 20 11 11 11 9 0 5 9 20 6 11 17 24 8 26 20 14 24 20 7 13 17 19 17 17 4 20 5 2 24 17 11 7 5 2 2 21 16 8 7 17 25 2 29 7 11 14 28 14 1 2 11 11 21 24 24 24 24 5 8 25 13 16 0 5 9 0 12 0 11 24 5 8 14 7 5 20 17 0 8 20 14 8 25 25 5 2 5 

p29:
19056
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 
20 11 13 2 20 5 2 9 14 17 22 16 8 20 3 14 14 17 5 11 2 0 5 3 5 8 19 24 5 24 5 25 6 25 20 20 24 15 0 14 0 14 15 8 24 14 0 13 27 8 29 14 14 5 13 20 17 11 0 14 0 5 20 11 11 11 9 0 9 9 20 6 11 17 24 8 26 20 14 24 20 7 13 17 17 17 17 4 20 5 2 24 17 11 17 5 2 2 21 16 8 17 17 25 2 29 17 11 14 28 14 1 2 11 11 21 24 24 24 24 5 8 25 13 16 0 5 9 0 12 0 11 24 29 8 14 7 5 20 17 0 8 20 14 8 25 25 5 2 5 

p30:
15990
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 
20 11 13 2 20 5 2 9 14 17 22 16 8 20 3 14 14 17 5 11 2 0 5 3 5 8 19 24 5 24 5 25 6 25 20 20 24 15 0 14 0 14 15 8 24 14 0 13 27 8 29 14 14 5 13 20 17 11 0 14 0 5 20 11 11 11 9 0 9 9 20 6 11 17 24 8 26 20 14 24 20 7 13 17 17 17 17 4 20 5 2 24 17 11 17 5 2 2 21 16 8 17 17 25 2 29 17 11 14 28 14 1 2 11 11 21 24 24 24 24 5 8 25 13 16 0 5 9 0 12 0 11 24 29 8 14 7 5 20 17 0 8 20 14 8 25 25 5 2 5 

p31:
21390
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 
20 11 13 2 20 5 2 9 14 17 22 16 8 20 3 14 14 17 5 11 2 0 5 3 5 8 19 24 5 24 5 25 6 25 20 20 24 15 0 14 0 14 15 8 24 14 0 13 27 8 29 14 14 5 13 20 17 11 0 14 0 5 20 11 11 11 9 0 9 9 20 6 11 17 24 8 26 20 14 24 20 7 13 17 17 17 17 4 20 5 2 24 17 11 17 5 2 2 21 16 8 17 17 25 2 29 17 11 14 28 14 1 2 11 11 21 24 24 24 24 5 8 25 13 16 0 5 9 0 12 0 11 24 29 8 14 7 5 20 17 0 8 20 14 8 25 25 5 2 5 

p32:
26790
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 
20 11 13 2 20 5 2 9 14 17 22 16 8 20 3 14 14 17 5 11 2 0 5 3 5 8 19 24 5 24 5 25 6 25 20 20 24 15 0 14 0 14 15 8 24 14 0 13 27 8 29 14 14 5 13 20 17 11 0 14 0 5 20 11 11 11 9 0 9 9 20 6 11 17 24 8 26 20 14 24 20 7 13 17 17 17 17 4 20 5 2 24 17 11 17 5 2 2 21 16 8 17 17 25 2 29 17 11 14 28 14 1 2 11 11 21 24 24 24 24 5 8 25 13 16 0 5 9 0 12 0 11 24 29 8 14 7 5 20 17 0 8 20 14 8 25 25 5 2 5 

p33:
19055
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 
20 11 13 2 20 5 2 9 14 17 22 16 8 20 3 14 14 17 5 11 2 0 5 3 5 8 19 24 5 24 5 25 6 25 20 20 24 15 0 14 0 14 15 8 24 14 0 13 27 8 29 14 14 5 13 20 17 11 0 14 0 5 20 11 11 11 9 0 5 9 20 6 11 17 24 8 26 20 14 24 20 7 13 17 17 17 17 4 20 5 2 24 17 11 17 5 2 2 21 16 8 17 17 25 2 29 17 11 14 28 14 1 2 11 11 21 24 24 24 24 5 8 25 13 16 0 5 9 0 12 0 11 24 5 8 14 7 5 20 17 0 8 20 14 8 25 25 5 2 5 

p34:
15989
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 
20 11 13 2 20 5 2 9 14 17 22 16 8 20 3 14 14 17 5 11 2 0 5 3 5 8 19 24 5 24 5 25 6 25 20 20 24 15 0 14 0 14 15 8 24 14 0 13 27 8 29 14 14 5 13 20 17 11 0 14 0 5 20 11 11 11 9 0 5 9 20 6 11 17 24 8 26 20 14 24 20 7 13 17 17 17 17 4 20 5 2 24 17 11 17 5 2 2 21 16 8 17 17 25 2 29 17 11 14 28 14 1 2 11 11 21 24 24 24 24 5 8 25 13 16 0 5 9 0 12 0 11 24 5 8 14 7 5 20 17 0 8 20 14 8 25 25 5 2 5 

p35:
21389
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 
20 11 13 2 20 5 2 9 14 17 22 16 8 20 3 14 14 17 5 11 2 0 5 3 5 8 19 24 5 24 5 25 6 25 20 20 24 15 0 14 0 14 15 8 24 14 0 13 27 8 29 14 14 5 13 20 17 11 0 14 0 5 20 11 11 11 9 0 5 9 20 6 11 17 24 8 26 20 14 24 20 7 13 17 17 17 17 4 20 5 2 24 17 11 17 5 2 2 21 16 8 17 17 25 2 29 17 11 14 28 14 1 2 11 11 21 24 24 24 24 5 8 25 13 16 0 5 9 0 12 0 11 24 5 8 14 7 5 20 17 0 8 20 14 8 25 25 5 2 5 

p36:
26789
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 
20 11 13 2 20 5 2 9 14 17 22 16 8 20 3 14 14 17 5 11 2 0 5 3 5 8 19 24 5 24 5 25 6 25 20 20 24 15 0 14 0 14 15 8 24 14 0 13 27 8 29 14 14 5 13 20 17 11 0 14 0 5 20 11 11 11 9 0 5 9 20 6 11 17 24 8 26 20 14 24 20 7 13 17 17 17 17 4 20 5 2 24 17 11 17 5 2 2 21 16 8 17 17 25 2 29 17 11 14 28 14 1 2 11 11 21 24 24 24 24 5 8 25 13 16 0 5 9 0 12 0 11 24 5 8 14 7 5 20 17 0 8 20 14 8 25 25 5 2 5 

p37:
19055
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 
20 11 13 2 20 5 2 9 14 17 22 16 8 20 3 14 14 17 5 11 2 0 5 3 5 8 19 24 5 24 5 25 6 25 20 20 24 15 0 14 0 14 15 8 24 14 0 13 27 8 29 14 14 5 13 20 17 11 0 14 0 5 20 11 11 11 9 0 5 9 20 6 11 17 24 8 26 20 14 24 20 7 13 17 17 17 17 4 20 5 2 24 17 11 17 5 2 2 21 16 8 17 17 25 2 29 17 11 14 28 14 1 2 11 11 21 24 24 24 24 5 8 25 13 16 0 5 9 0 12 0 11 24 5 8 14 7 5 20 17 0 8 20 14 8 25 25 5 2 5 

p38:
15989
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 
20 11 13 2 20 5 2 9 14 17 22 16 8 20 3 14 14 17 5 11 2 0 5 3 5 8 19 24 5 24 5 25 6 25 20 20 24 15 0 14 0 14 15 8 24 14 0 13 27 8 29 14 14 5 13 20 17 11 0 14 0 5 20 11 11 11 9 0 5 9 20 6 11 17 24 8 26 20 14 24 20 7 13 17 17 17 17 4 20 5 2 24 17 11 17 5 2 2 21 16 8 17 17 25 2 29 17 11 14 28 14 1 2 11 11 21 24 24 24 24 5 8 25 13 16 0 5 9 0 12 0 11 24 5 8 14 7 5 20 17 0 8 20 14 8 25 25 5 2 5 

p39:
21389
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 
20 11 13 2 20 5 2 9 14 17 22 16 8 20 3 14 14 17 5 11 2 0 5 3 5 8 19 24 5 24 5 25 6 25 20 20 24 15 0 14 0 14 15 8 24 14 0 13 27 8 29 14 14 5 13 20 17 11 0 14 0 5 20 11 11 11 9 0 5 9 20 6 11 17 24 8 26 20 14 24 20 7 13 17 17 17 17 4 20 5 2 24 17 11 17 5 2 2 21 16 8 17 17 25 2 29 17 11 14 28 14 1 2 11 11 21 24 24 24 24 5 8 25 13 16 0 5 9 0 12 0 11 24 5 8 14 7 5 20 17 0 8 20 14 8 25 25 5 2 5 

p40:
26789
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 
20 11 13 2 20 5 2 9 14 17 22 16 8 20 3 14 14 17 5 11 2 0 5 3 5 8 19 24 5 24 5 25 6 25 20 20 24 15 0 14 0 14 15 8 24 14 0 13 27 8 29 14 14 5 13 20 17 11 0 14 0 5 20 11 11 11 9 0 5 9 20 6 11 17 24 8 26 20 14 24 20 7 13 17 17 17 17 4 20 5 2 24 17 11 17 5 2 2 21 16 8 17 17 25 2 29 17 11 14 28 14 1 2 11 11 21 24 24 24 24 5 8 25 13 16 0 5 9 0 12 0 11 24 5 8 14 7 5 20 17 0 8 20 14 8 25 25 5 2 5 

p41:
7107
1 1 1 1 1 1 1 1 1 1 
5 6 4 1 7 9 3 7 8 8 4 6 2 6 2 7 7 3 0 6 6 1 4 1 6 5 5 4 8 5 8 0 0 0 3 9 2 6 6 2 2 7 3 3 3 5 0 5 6 4 1 1 6 6 9 7 2 8 8 8 0 0 1 5 0 6 6 6 4 4 0 4 4 0 7 7 2 2 6 5 7 2 2 7 9 9 9 9 9 9 

p42:
9957
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
12 10 11 9 15 18 16 3 17 1 11 18 6 10 6 15 0 2 14 14 5 11 9 8 12 8 11 16 17 13 7 19 6 8 14 10 10 0 0 1 1 3 3 16 9 5 8 19 15 15 16 17 7 13 13 5 2 14 14 14 11 11 4 3 11 3 0 15 19 6 10 18 19 19 19 18 18 18 19 19 

p43:
12448
1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 
18 19 15 24 25 22 26 21 27 29 24 23 3 9 18 11 8 15 12 7 25 26 22 20 17 13 29 6 29 4 5 2 2 13 0 22 7 12 21 11 4 12 28 23 5 25 26 17 17 11 21 0 9 18 6 6 19 20 2 29 5 27 1 29 27 28 1 27 28 29 

p44:
7215
1 1 1 1 1 1 1 1 1 1 
4 4 4 4 4 4 4 4 6 0 0 0 0 0 0 0 1 1 1 8 1 1 6 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 4 0 1 1 2 8 7 5 9 7 7 6 5 5 9 8 7 7 9 5 5 5 9 3 0 6 6 8 1 5 4 9 5 7 7 8 6 6 5 2 7 9 9 9 9 9 6 5 7 5 

p45:
9848
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
0 0 0 0 0 0 0 1 1 1 1 6 6 6 6 2 2 3 2 3 2 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 0 0 2 3 11 12 18 16 19 7 15 16 8 13 11 16 18 19 14 15 10 9 12 9 15 17 13 13 8 12 7 10 18 12 13 17 14 17 8 16 10 7 

p46:
12639
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 
10 0 10 10 10 0 10 1 1 1 1 11 11 11 11 2 2 3 2 3 2 4 4 5 6 6 5 7 7 8 7 8 9 9 10 2 3 17 24 28 29 12 21 22 24 14 18 17 16 28 29 27 13 22 25 26 13 18 18 24 19 15 28 18 26 27 14 13 15 12 

p47:
6593
1 1 1 1 1 1 1 1 1 1 
0 0 0 0 0 0 0 0 0 1 1 2 1 1 1 2 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 6 7 6 0 7 7 7 7 7 7 8 8 8 8 9 8 6 9 6 2 9 9 9 8 9 0 

p48:
9044
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
0 0 0 0 1 0 1 1 1 2 3 2 2 3 3 4 4 4 5 5 5 5 5 5 6 6 6 6 6 7 7 8 8 8 8 8 8 8 9 9 9 9 10 10 11 10 11 10 12 13 12 13 13 12 13 14 15 12 14 12 0 15 14 14 15 16 16 17 17 17 17 17 17 18 18 19 18 19 19 19 

p49:
12420
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 
0 1 1 2 1 2 2 2 3 5 3 5 4 6 6 6 7 7 7 7 7 7 9 10 8 11 10 12 12 14 13 13 13 14 15 15 16 16 17 16 17 16 20 19 18 19 18 20 21 18 21 18 0 22 23 23 22 24 24 26 25 26 25 26 27 27 28 27 28 28 

p50:
9848
1 1 1 1 1 1 1 1 1 1 
3 6 3 0 2 1 5 5 3 7 7 4 1 9 0 9 9 2 5 3 0 0 0 4 0 4 7 4 4 7 7 7 3 3 3 5 9 1 0 6 0 9 1 9 5 5 5 5 5 3 3 5 6 4 0 0 6 6 2 2 1 7 7 7 3 3 6 4 8 7 3 0 6 0 0 4 4 3 3 4 3 5 2 2 2 2 6 7 2 7 9 1 1 2 1 1 9 9 9 9 

p51:
11340
1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 
15 6 19 10 12 13 5 16 15 1 5 3 6 13 6 13 12 16 2 15 0 0 10 14 14 14 1 3 19 7 1 1 17 19 15 5 13 13 10 0 0 13 13 13 16 5 5 5 5 17 15 2 0 14 14 10 6 6 18 12 13 5 1 5 15 15 10 3 7 7 15 0 0 0 10 19 19 19 19 3 19 5 16 12 18 13 6 8 12 1 13 13 13 4 13 13 13 13 13 13 

p52:
10388
1 1 1 1 1 1 1 1 1 1 
7 7 7 7 7 7 7 7 3 4 4 4 3 4 4 4 4 8 8 8 8 3 3 8 3 5 5 9 9 9 9 9 9 9 6 6 6 6 6 6 6 6 6 6 7 7 4 8 8 5 5 3 4 6 2 5 3 3 3 4 6 9 5 5 0 5 9 6 4 7 6 6 4 3 3 5 3 4 7 1 6 3 3 5 5 3 3 7 3 3 5 5 9 1 5 1 3 4 3 7 

p53:
12432
1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 
5 5 5 5 5 5 5 5 19 19 19 7 7 7 7 7 7 12 13 12 12 13 12 12 3 15 9 9 9 9 9 9 9 9 18 18 18 18 18 18 18 18 18 18 5 5 7 12 12 15 15 4 7 18 5 11 3 3 1 6 18 2 15 13 0 13 2 5 6 5 17 18 6 3 3 15 3 6 6 2 14 19 13 15 15 3 1 6 15 1 2 2 17 17 2 17 1 6 1 16 

p54:
9556
1 1 1 1 1 1 1 1 1 1 
7 7 7 7 7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 3 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 6 6 8 8 6 8 8 8 8 8 8 6 3 6 6 6 6 6 6 6 6 6 5 5 6 5 5 5 6 6 0 0 6 0 5 7 0 0 0 0 0 0 0 0 4 4 4 4 4 4 4 4 9 4 9 9 9 4 9 9 9 

p55:
11889
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 
17 17 16 17 16 4 4 4 8 8 8 8 2 8 2 8 2 2 8 12 1 12 12 6 12 12 12 6 6 6 6 14 14 6 6 6 6 6 6 7 7 19 19 7 0 0 0 0 0 0 0 0 7 7 7 7 7 7 7 7 11 11 11 11 3 11 11 7 11 9 9 11 9 11 17 13 9 13 9 9 13 15 15 15 15 15 15 15 5 15 5 18 18 18 18 17 18 18 18 18 

p56:
23882
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19 

p57:
32882
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19 

p58:
53882
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19 

p59:
39121
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19 

p60:
23882
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19 

p61:
32882
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19 

p62:
53882
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19 

p63:
39121
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19 

p64:
23882
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19 

p65:
32882
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19 

p66:
53882
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19 

p67:
39671
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
18 19 21 22 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 15 18 9 6 26 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 25 29 0 7 8 13 11 5 14 28 25 7 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 19 5 27 7 28 6 25 25 2 3 27 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19 

p68:
23882
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19 

p69:
32882
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19 

p70:
53882
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19 

p71:
39121
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19

模拟退火算法:

模拟退火求出来的也是近似解, 其特点在于可以跳出局部最优解, 以一定概率落到全局最优解处

模拟退火参数:
  1. 初温 100, 末温 0.0001, 降温比例 0.96
  2. 内循环次数 200
生成邻域操作:
  1. 随机选两个顾客, 随机安排到两个设施
  2. 随机选三个顾客, 循环左移它们的设施安排
  3. 随机选一个顾客, 随机安排到一个设施
  4. 随机选两个顾客, 交换它们的设施安排
邻域操作的解释:

对于 1和2, 是在温度较高时, 大幅度在搜索空间跳跃, 加大搜索范围;
对于 3和4, 是在温度较低时, 轻微的改变解的结构, 来寻找当前更优解;

结果:
序号 成本 时间 序号 成本 时间 序号 成本 时间
1 8985 0.047 25 14304 0.207 49 6121 0.096
2 7920 0.045 26 12219 0.207 50 9279 0.046
3 9720 0.045 27 14746 0.215 51 8898 0.093
4 11189 0.047 28 16651 0.212 52 9376 0.048
5 9169 0.047 29 13930 0.214 53 9777 0.093
6 7855 0.046 30 12182 0.21 54 9483 0.046
7 9769 0.047 31 15130 0.213 55 9600 0.096
8 11566 0.047 32 17531 0.212 56 24550 0.276
9 8769 0.042 33 13085 0.211 57 30740 0.274
10 7704 0.042 34 12047 0.206 58 48921 0.279
11 9233 0.043 35 14608 0.208 59 35904 0.276
12 10638 0.042 36 17509 0.21 60 24663 0.274
13 8539 0.047 37 12739 0.21 61 31979 0.272
14 7506 0.044 38 11985 0.208 62 51028 0.275
15 9413 0.043 39 13618 0.21 63 37762 0.277
16 11069 0.045 40 17244 0.208 64 24000 0.273
17 8800 0.044 41 7116 0.043 65 31581 0.28
18 7392 0.045 42 7349 0.073 66 47431 0.276
19 9151 0.043 43 7331 0.1 67 36247 0.276
20 11156 0.046 44 7138 0.046 68 23533 0.271
21 8600 0.044 45 8033 0.069 69 31596 0.276
22 7727 0.043 46 7048 0.097 70 48181 0.271
23 9609 0.043 47 6254 0.044 71 36649 0.271
24 11272 0.046 48 6709 0.073
分配方法:
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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355

p1:
8985
1 1 1 1 1 1 1 0 1 1 
8 2 1 6 3 8 2 4 4 1 9 0 3 2 8 3 4 0 9 4 3 4 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 0 4 1 8 1 5 4 0 2 0 4 0 

p2:
7920
1 1 1 1 1 1 1 0 1 1 
8 2 1 6 3 8 2 4 4 1 9 0 3 2 8 3 4 0 9 4 3 4 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 0 4 1 8 1 5 4 0 2 0 4 0 

p3:
9720
1 1 1 1 1 1 1 0 1 1 
8 2 1 6 3 8 2 4 4 1 9 0 3 2 8 3 4 0 9 4 3 4 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 0 4 1 8 1 5 4 0 2 0 4 0 

p4:
11189
1 1 1 1 1 1 1 0 1 0 
2 2 1 6 3 8 2 4 4 1 4 8 3 2 8 3 2 0 6 4 3 8 6 4 2 5 1 5 0 5 2 6 0 3 4 4 4 3 0 4 1 8 1 5 4 0 2 0 4 0 

p5:
9169
1 1 1 1 1 1 1 1 1 1 
8 8 1 6 3 8 2 4 4 1 9 8 3 2 8 3 4 0 9 7 3 8 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 0 4 1 8 1 5 7 0 2 3 7 0 

p6:
7855
1 1 1 1 1 1 1 1 1 1 
8 8 1 6 3 8 2 4 4 1 9 8 3 2 8 3 4 0 9 7 3 8 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 0 4 1 8 1 5 7 0 2 3 7 0 

p7:
9769
1 1 1 1 1 1 1 1 1 0 
8 8 1 6 3 8 2 4 4 1 4 8 3 2 8 3 2 0 6 7 3 8 6 4 2 5 1 5 0 5 6 6 0 3 4 4 7 3 0 4 1 8 1 5 7 0 2 3 4 0 

p8:
11566
1 1 1 1 1 1 1 0 1 1 
8 8 1 6 3 8 2 4 4 1 9 8 3 2 8 3 2 0 9 9 3 8 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 0 4 1 8 1 5 4 0 9 3 4 0 

p9:
8769
1 1 1 1 1 1 1 0 1 1 
8 8 1 6 3 8 2 4 4 1 9 8 3 2 8 3 4 0 9 4 3 8 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 0 4 1 8 1 5 4 0 2 0 4 0 

p10:
7704
1 1 1 1 1 1 1 0 1 1 
8 8 1 6 3 8 2 4 4 1 9 8 3 2 8 3 4 0 9 4 3 8 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 0 4 1 8 1 5 4 0 2 0 4 0 

p11:
9233
1 0 1 1 1 1 1 0 1 0 
8 8 5 6 3 8 2 4 4 5 4 8 3 2 8 3 2 0 6 4 3 8 6 4 2 5 3 5 0 5 2 6 0 3 4 4 4 3 0 4 3 8 3 5 4 0 2 0 4 0 

p12:
10638
1 0 1 1 1 1 1 0 1 0 
8 8 5 6 3 8 2 4 4 5 4 8 0 2 8 3 2 0 6 4 3 8 6 4 2 5 3 5 0 5 2 6 0 3 4 4 4 3 0 4 3 8 3 5 4 0 2 0 4 0 

p13:
8539
1 1 0 0 0 0 1 0 0 1 1 0 1 1 0 1 0 1 0 1 
0 12 10 10 1 1 17 13 12 17 15 19 1 6 13 12 15 10 17 9 12 15 15 19 6 1 0 17 1 17 13 15 13 0 1 10 17 19 19 13 6 0 15 0 9 13 12 10 19 9 

p14:
7506
1 1 0 1 0 0 1 0 0 0 1 0 0 1 1 1 0 1 0 1 
0 1 10 10 1 13 17 13 14 17 15 1 1 6 13 3 15 10 17 6 14 15 15 19 6 1 0 17 1 17 13 14 13 0 3 10 3 19 19 13 6 0 15 0 3 15 14 10 19 6 

p15:
9413
0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 1 
16 12 10 10 1 12 17 13 12 17 15 19 1 6 13 3 15 10 17 6 12 15 15 19 6 1 16 17 1 17 13 15 13 16 3 10 3 19 19 13 6 16 15 16 3 13 12 10 19 6 

p16:
11069
1 0 0 1 0 0 1 0 0 0 1 0 0 1 1 1 0 1 0 1 
0 3 10 10 19 13 17 13 14 17 15 19 19 6 13 3 15 10 17 6 14 15 15 19 6 17 0 3 3 17 13 14 13 0 3 10 3 14 19 13 6 0 15 0 3 13 14 10 19 6 

p17:
8800
1 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 1 0 1 
0 1 10 10 1 13 17 13 12 17 15 19 1 6 13 11 15 10 17 6 12 15 15 19 6 17 0 17 1 17 13 15 13 0 1 10 11 19 19 13 6 0 15 0 11 13 12 6 19 6 

p18:
7392
0 1 0 0 0 0 1 0 0 0 1 1 0 1 1 1 1 1 0 1 
16 1 10 10 1 15 17 13 14 17 15 19 1 6 13 11 15 10 17 6 14 15 15 19 6 17 16 17 1 17 13 15 13 16 1 10 11 1 19 13 6 16 15 16 11 13 14 10 19 11 

p19:
9151
0 1 0 0 0 0 1 0 0 0 1 0 0 1 1 1 1 1 0 1 
16 1 10 10 1 15 17 13 14 17 15 19 1 6 13 14 15 10 17 6 14 15 15 19 6 1 16 17 1 17 13 15 13 16 1 10 17 19 19 13 6 16 15 16 6 13 14 10 19 6 

p20:
11156
0 0 0 1 0 0 0 0 1 0 1 0 0 1 1 1 1 1 0 1 
16 3 10 10 14 15 17 13 14 17 15 19 19 10 13 3 15 10 17 8 14 15 15 19 14 17 16 17 3 17 13 15 13 16 3 10 3 19 19 13 14 16 15 16 8 13 14 10 19 8 

p21:
8600
0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 1 0 1 
16 1 10 10 1 13 17 13 14 17 5 19 1 10 13 14 5 10 17 9 14 5 5 19 9 17 16 17 1 17 13 14 13 16 1 10 17 1 19 13 9 16 5 16 9 5 14 10 19 9 

p22:
7727
0 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0 1 1 0 1 
16 1 10 10 1 19 17 13 14 17 7 19 1 6 13 3 7 10 17 9 14 5 7 19 6 17 16 17 1 17 13 7 13 16 3 10 3 19 19 13 6 16 5 16 3 5 14 10 19 9 

p23:
9609
1 1 0 0 0 0 0 0 1 0 1 0 1 1 0 1 1 1 0 1 
16 12 10 10 1 15 17 13 12 17 15 19 1 10 13 12 15 10 17 8 12 15 15 19 10 17 16 17 1 17 13 15 13 16 1 10 8 19 19 13 10 0 0 0 8 13 12 10 19 8 

p24:
11272
0 0 1 1 0 0 0 0 1 0 1 0 0 0 1 1 1 1 0 1 
16 3 10 10 19 15 17 2 14 17 15 19 19 10 2 3 15 10 17 8 14 15 15 19 10 17 16 17 3 17 2 14 2 16 3 10 3 19 19 2 10 16 15 16 8 15 14 10 19 8 

p25:
14304
1 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 0 1 0 1 1 0 0 0 1 1 0 0 0 1 
20 11 20 14 8 5 17 24 14 17 9 8 8 20 19 14 14 17 5 11 2 0 5 7 5 8 19 24 5 9 5 25 20 25 20 20 24 9 7 14 0 14 24 8 24 14 0 20 11 8 29 19 14 5 20 20 2 29 0 14 0 5 20 11 0 11 24 0 5 9 8 8 25 17 24 8 24 20 14 9 20 7 20 17 2 17 2 7 20 5 2 24 17 11 7 5 14 19 25 2 14 7 17 25 2 29 7 11 14 8 14 2 2 11 25 25 24 24 24 24 5 8 25 20 8 0 5 9 11 25 0 11 24 5 8 14 0 5 20 17 0 8 20 14 8 0 25 5 2 5 

p26:
12219
1 0 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 0 1 
13 11 13 14 20 5 2 24 2 17 5 8 8 20 7 14 17 17 25 11 2 11 5 17 29 8 2 24 5 5 29 25 13 25 20 20 24 24 0 14 0 14 24 14 24 14 11 20 25 8 0 14 14 5 20 20 17 25 11 14 0 5 20 11 11 11 24 0 25 24 13 20 11 17 24 8 24 20 14 24 20 7 20 0 2 17 0 0 20 5 2 24 17 11 7 5 2 0 25 20 14 7 17 25 2 29 0 11 14 8 14 14 2 11 25 29 24 24 5 24 5 8 11 13 20 0 5 24 0 5 0 11 24 24 20 14 0 5 20 17 0 20 20 14 8 11 11 5 2 5 

p27:
14746
1 0 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 
20 11 20 2 20 5 17 24 8 17 5 8 8 20 7 14 14 17 5 11 14 2 5 0 5 8 17 24 5 24 5 25 13 25 20 20 24 24 0 14 0 8 24 14 24 14 7 13 11 8 5 14 14 5 13 20 17 11 0 14 0 5 20 27 11 11 24 0 24 11 13 20 11 17 24 8 24 20 14 24 20 7 20 17 0 17 2 7 20 5 2 24 17 11 7 5 2 2 27 20 20 7 14 11 2 25 7 11 14 14 14 14 2 11 25 27 24 24 24 24 5 8 25 13 8 0 5 5 11 25 0 11 24 27 8 14 0 5 20 17 0 8 20 14 8 25 25 5 2 5 

p28:
16651
1 0 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 
20 25 13 2 20 5 2 24 8 17 24 20 8 20 7 14 14 17 25 11 2 0 5 7 5 8 2 24 24 24 5 25 20 25 20 20 24 24 25 14 0 14 24 14 24 14 0 13 11 8 5 14 14 5 20 20 17 25 0 14 0 24 20 11 11 11 24 0 24 24 20 20 11 0 24 8 24 20 17 24 20 7 20 17 17 17 17 0 20 5 14 24 17 11 7 24 2 2 25 20 20 7 17 25 2 25 7 11 14 8 14 0 2 11 11 25 24 24 24 24 5 14 25 13 20 0 5 24 0 11 0 0 24 5 8 14 7 5 20 17 0 8 20 14 8 25 25 5 2 5 

p29:
13930
1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 0 1 
20 11 13 14 13 5 2 9 14 17 9 8 8 20 2 14 14 17 5 11 2 0 9 2 9 8 2 24 5 24 25 25 13 25 20 20 24 24 0 14 0 14 5 8 24 14 0 13 11 8 29 17 14 5 13 20 17 11 0 14 0 5 20 11 11 11 24 0 9 29 20 13 11 17 24 8 24 20 14 24 20 0 13 17 2 17 17 0 20 29 2 24 17 11 17 5 2 2 11 13 20 17 17 25 2 29 0 11 14 8 14 14 2 11 11 25 24 24 5 24 5 8 25 13 8 17 5 9 0 25 0 11 24 29 8 14 17 5 20 17 0 8 20 14 8 25 25 5 2 5 

p30:
12182
1 0 1 0 0 1 0 1 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 
13 11 20 2 20 5 2 9 8 17 24 8 8 20 17 14 14 17 5 11 2 7 9 17 9 8 14 24 5 9 5 25 13 25 20 20 24 24 0 14 0 14 24 8 24 14 7 13 11 8 11 2 14 5 13 20 17 11 0 14 0 5 20 0 11 11 9 0 9 9 20 13 11 0 24 20 9 20 14 24 13 7 13 17 7 17 2 0 20 5 2 24 17 11 17 5 2 2 25 13 8 7 17 25 2 25 17 11 8 8 14 14 2 11 11 5 24 24 24 24 5 8 25 13 8 0 25 9 0 11 0 11 24 25 8 14 0 5 20 17 0 8 20 14 8 25 25 5 17 5 

p31:
15130
1 0 1 0 0 1 0 1 1 1 0 1 0 1 1 0 0 1 1 0 1 0 0 0 1 1 0 0 0 0 
13 11 13 2 20 5 2 9 14 17 25 8 8 20 2 14 14 17 5 11 2 17 5 17 25 8 2 24 5 24 25 25 13 25 20 20 24 24 7 14 0 14 24 8 24 14 0 13 25 8 25 7 14 5 20 20 17 11 0 14 0 5 20 0 11 11 9 0 9 9 20 13 11 17 24 8 24 20 14 9 20 7 13 17 2 17 17 0 20 5 2 24 17 11 17 9 2 2 11 18 8 7 17 25 2 25 7 11 14 8 14 2 2 11 11 25 24 24 24 24 5 8 25 13 18 7 5 9 11 25 0 0 24 0 8 14 7 5 20 17 0 8 20 14 8 25 25 5 2 5 

p32:
17531
1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 1 1 0 0 0 1 1 0 0 0 0 
20 25 13 14 13 5 19 9 14 17 9 8 8 20 19 14 14 17 5 11 2 0 5 17 25 8 19 24 5 9 5 25 13 25 20 20 24 24 11 14 0 14 24 13 24 14 17 13 11 8 25 2 14 5 13 20 17 11 11 14 0 5 20 11 11 11 9 0 9 9 20 13 11 17 24 8 9 20 2 24 20 17 13 17 2 17 17 0 20 5 2 24 17 11 0 5 17 19 25 8 8 17 14 25 2 5 0 0 20 8 14 2 2 11 25 24 24 24 24 24 5 8 25 13 8 0 5 9 17 25 0 11 24 5 8 14 0 5 20 17 0 20 20 14 8 25 25 11 2 5 

p33:
13085
1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 
20 11 20 14 20 5 17 24 14 17 5 16 8 20 17 14 14 17 5 11 2 0 5 17 5 8 2 24 5 24 25 25 16 25 20 20 24 24 0 14 0 14 24 16 24 14 7 20 11 8 25 14 14 5 20 20 17 0 0 14 0 5 20 11 11 11 24 0 5 5 8 20 5 17 24 8 24 20 14 24 20 7 20 17 17 17 17 7 20 25 2 24 17 11 7 24 2 2 25 16 20 0 17 25 2 25 17 11 14 8 14 14 2 11 11 11 24 24 24 24 5 8 25 20 20 0 5 24 0 25 0 25 24 25 8 14 7 5 20 17 0 8 20 14 8 25 25 5 2 5 

p34:
12047
1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 
20 11 20 2 13 5 2 9 20 17 9 8 8 20 2 14 14 17 5 11 2 0 5 2 5 8 2 24 5 24 5 25 20 25 20 20 24 24 27 14 0 14 24 8 24 14 11 20 27 8 25 14 14 5 20 20 17 27 11 14 0 5 20 11 11 11 9 0 24 9 8 13 11 17 24 8 24 20 2 9 20 0 13 17 17 17 17 17 20 5 2 24 17 11 17 9 14 2 25 14 8 17 17 25 2 25 17 11 14 8 14 14 2 11 11 27 24 24 5 24 5 8 25 13 8 0 5 9 0 25 0 11 24 24 14 14 17 5 20 17 0 8 20 14 8 17 25 5 2 5 

p35:
14608
1 0 1 0 0 1 0 1 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 
20 11 20 14 8 5 2 9 14 17 24 8 8 20 17 14 14 17 5 11 2 0 5 2 5 8 2 24 5 24 5 25 13 11 20 20 24 24 7 14 0 8 24 14 24 14 0 13 11 8 5 14 14 5 20 20 17 25 0 14 0 5 20 11 11 11 24 0 9 9 20 20 11 17 24 8 24 20 14 24 20 7 13 17 2 17 17 0 20 5 17 24 17 11 17 5 2 2 5 13 8 17 17 25 2 25 17 11 14 8 14 14 2 11 11 25 24 24 24 5 5 14 25 13 8 0 5 9 7 11 0 0 24 5 8 14 17 5 20 17 0 8 20 14 8 25 25 5 2 5 

p36:
17509
1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 1 0 
20 11 20 2 20 5 2 9 28 17 5 8 28 20 2 28 17 17 5 11 14 0 5 17 5 8 2 24 5 9 5 25 13 25 20 20 24 24 0 14 0 8 24 28 24 14 0 13 11 8 5 14 14 5 20 20 2 11 11 14 0 24 20 0 11 11 24 0 5 9 20 20 11 17 24 8 24 20 14 9 20 0 20 17 0 17 17 17 20 5 2 24 17 0 17 9 2 25 11 2 28 17 17 25 2 25 17 11 14 14 14 2 2 11 11 25 24 24 24 24 5 8 5 13 20 0 5 0 11 25 0 17 24 25 28 14 0 5 20 17 0 8 20 14 8 25 25 5 2 5 

p37:
12739
1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 
20 11 20 14 20 5 2 24 8 17 5 20 8 20 7 14 14 17 25 11 17 0 5 17 25 8 2 24 5 24 5 25 20 25 20 20 24 24 25 14 0 14 24 8 24 14 17 20 25 14 25 2 14 5 20 20 17 25 11 14 0 5 20 11 11 11 24 0 5 5 20 20 11 17 24 8 24 20 14 24 20 7 20 17 17 17 17 7 20 25 2 24 17 11 17 5 2 2 25 20 8 17 17 25 2 25 7 11 14 8 14 2 2 11 11 0 24 24 24 24 5 8 25 20 8 7 5 24 0 11 0 0 24 25 8 14 17 5 20 17 0 20 20 14 8 25 25 5 2 5 

p38:
11985
1 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 
20 11 20 14 20 5 17 9 14 17 9 16 8 20 7 14 14 17 5 11 14 0 9 7 5 8 2 24 5 24 5 25 20 25 20 20 24 24 25 14 0 14 24 16 24 14 17 20 11 8 25 14 14 5 20 20 17 0 0 14 0 5 20 0 11 11 9 0 5 24 20 20 11 17 24 8 24 20 14 24 20 7 20 17 2 17 17 0 20 5 2 24 17 11 17 24 2 2 25 16 8 17 17 25 2 25 17 11 14 8 14 14 2 11 11 5 24 24 24 24 5 8 5 20 8 0 5 9 0 11 0 0 24 5 20 14 7 5 20 17 0 8 20 14 8 11 25 5 2 5 

p39:
13618
1 0 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 
20 11 13 14 20 5 14 24 14 17 5 20 8 20 2 14 14 17 5 11 2 0 5 2 5 8 17 24 5 24 5 25 20 25 20 20 24 24 0 14 0 14 24 14 24 14 0 13 11 8 5 14 14 5 13 20 17 0 0 14 0 5 20 11 11 11 24 0 5 5 20 13 11 17 24 8 24 20 14 24 20 0 13 17 17 17 17 0 20 5 2 24 17 11 0 24 2 0 25 20 8 17 17 25 2 25 17 11 14 8 14 0 2 11 11 5 24 24 24 24 5 20 25 13 8 0 5 24 0 0 0 11 24 0 8 14 0 5 20 17 0 8 20 14 8 25 25 5 2 5 

p40:
17244
1 0 1 0 0 1 0 1 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 
20 11 20 14 13 5 17 24 14 17 9 8 8 20 7 14 14 17 25 11 14 0 5 17 5 8 2 24 5 24 5 25 20 25 20 20 24 24 0 14 0 14 24 14 24 14 17 13 11 8 25 14 14 5 20 13 17 5 0 14 0 5 20 0 11 11 9 0 24 9 20 20 11 17 24 8 24 20 14 5 20 7 13 17 2 17 17 7 20 5 2 24 2 0 17 24 2 2 25 13 8 17 17 25 2 25 17 0 14 8 14 14 2 11 11 25 24 24 24 24 5 8 11 13 8 0 5 9 7 11 0 0 24 5 8 14 7 5 20 17 0 8 20 14 8 11 25 5 2 5 

p41:
7116
1 1 1 1 1 1 1 1 1 1 
5 6 4 1 7 9 3 7 8 8 4 6 2 6 2 7 7 3 0 6 6 1 4 1 6 5 5 4 8 5 8 0 0 0 3 9 2 6 6 9 2 7 3 3 3 5 0 5 6 4 1 1 6 6 9 7 2 8 8 8 0 0 1 5 0 6 6 6 4 4 0 0 4 0 7 7 2 2 6 5 7 2 9 7 9 9 9 2 9 2 

p42:
7349
0 1 1 1 0 1 1 0 1 0 0 1 0 0 1 1 1 0 1 1 
2 14 11 5 15 18 16 3 16 1 11 18 6 19 6 15 15 2 14 14 5 11 5 8 8 8 11 16 2 3 1 19 6 8 14 6 6 15 1 1 1 3 3 16 11 5 8 19 15 15 16 1 1 3 2 5 2 14 14 14 11 11 3 3 11 3 16 15 19 6 18 18 19 19 19 18 18 18 19 19 

p43:
7331
0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 1 1 0 
18 19 18 24 3 9 26 7 1 27 24 1 3 9 18 18 19 18 12 7 26 26 9 19 9 3 28 18 27 27 27 24 24 3 19 9 7 7 12 18 27 12 28 28 28 26 3 9 9 18 19 7 9 18 18 18 12 19 1 27 24 27 1 28 27 28 1 28 28 28 

p44:
7138
1 1 1 1 1 1 1 1 1 1 
4 4 4 4 4 4 4 4 6 0 0 0 0 0 0 0 1 8 1 7 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 4 0 1 1 2 8 7 5 9 7 7 6 5 5 8 8 7 7 9 5 5 5 9 3 0 6 6 8 1 5 4 9 5 7 7 8 6 6 5 8 7 9 9 9 9 9 6 5 7 5 

p45:
8033
1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 1 1 1 1 0 
0 0 0 0 0 0 0 1 1 1 10 1 1 15 15 2 2 3 2 3 2 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 0 0 2 2 11 3 18 16 18 3 15 16 13 13 11 16 18 16 16 15 10 10 12 2 15 17 13 13 11 12 10 10 18 12 13 17 17 17 11 16 10 13 

p46:
7048
0 1 1 1 0 0 1 1 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 
10 28 10 10 10 10 10 1 1 11 1 11 1 11 11 2 3 3 2 3 2 6 6 6 6 6 6 7 7 7 7 13 9 9 10 2 3 6 3 28 28 3 2 28 3 18 18 13 13 28 10 13 13 11 2 18 13 18 18 18 2 11 28 18 13 13 3 13 1 18 

p47:
6254
1 1 1 1 1 1 1 1 1 1 
0 0 0 0 0 0 2 0 0 0 1 1 1 2 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 6 7 6 0 7 7 7 7 7 7 8 8 8 8 6 8 8 8 9 2 9 9 9 0 9 9 

p48:
6709
1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 0 
0 0 0 0 1 0 1 1 1 2 2 2 2 2 2 5 5 5 5 5 5 5 5 5 7 7 7 7 7 7 7 8 8 8 9 8 8 8 9 9 9 9 11 11 11 11 8 11 13 13 12 13 12 12 13 15 15 12 15 12 0 15 15 15 15 17 17 17 17 17 17 17 13 17 17 17 0 0 0 0 

p49:
6121
0 0 1 0 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 
2 2 2 2 2 2 2 2 5 5 5 5 5 6 6 6 6 6 6 6 14 6 11 6 11 11 11 13 14 14 13 13 13 14 13 14 18 18 18 13 13 13 18 14 18 18 18 18 22 18 22 18 2 22 22 22 22 25 25 25 25 25 25 25 28 28 28 28 25 28 

p50:
9279
1 1 1 1 1 1 1 1 0 1 
3 6 3 0 2 9 5 5 3 7 7 4 1 9 0 9 9 5 5 3 6 0 0 4 0 4 7 4 4 7 7 7 3 3 3 5 1 9 0 6 0 9 9 9 5 5 5 5 5 3 3 5 6 0 0 0 9 6 1 2 9 7 7 7 3 3 0 4 7 7 3 6 6 6 0 4 4 3 3 4 3 5 2 2 2 2 6 7 2 7 9 1 2 2 1 2 1 9 1 1 

p51:
8898
1 1 0 0 0 1 1 0 0 0 1 0 1 1 1 1 1 0 1 1 
15 6 19 10 12 13 5 16 15 1 5 14 6 13 6 13 12 16 5 15 0 0 10 14 14 10 15 19 19 1 1 1 19 19 15 5 13 13 10 0 0 13 13 13 16 5 5 5 5 15 15 5 0 14 14 10 6 0 13 12 12 5 1 5 15 15 10 19 1 1 15 0 0 0 10 19 19 19 19 14 19 5 12 12 18 13 6 5 12 1 13 13 13 18 18 13 13 13 13 13 

p52:
9376
0 0 0 1 1 1 1 1 1 1 
7 7 7 7 7 7 7 7 3 4 4 4 3 4 4 4 4 8 3 8 8 3 3 8 3 5 9 9 9 9 9 9 9 5 6 6 6 6 6 6 6 6 6 6 7 7 4 8 8 5 5 3 4 6 7 9 3 3 3 4 6 9 5 5 3 8 5 7 4 7 6 6 4 3 3 5 3 4 7 5 6 4 8 5 5 3 3 7 5 3 5 8 9 6 5 6 3 4 3 7 

p53:
9777
0 1 1 1 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 1 
5 5 5 5 5 5 5 5 19 19 19 7 7 7 7 7 7 12 3 12 12 3 3 12 12 15 9 9 9 9 15 9 9 9 18 18 18 18 18 18 18 18 18 18 5 5 7 12 12 15 15 1 19 18 5 15 3 3 1 7 18 2 15 15 19 3 2 18 3 5 18 18 7 3 3 15 3 7 7 15 18 19 3 15 15 3 1 5 15 19 15 2 9 2 9 18 1 19 1 5 

p54:
9483
1 0 1 1 1 1 1 1 1 1 
9 7 7 7 7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 2 3 3 2 3 3 3 3 3 3 3 3 3 3 3 3 3 6 6 8 6 8 8 8 8 8 8 8 3 3 6 6 6 6 6 6 6 6 0 5 5 5 5 5 5 6 6 0 0 0 0 6 7 0 0 0 0 0 0 4 0 4 4 4 4 4 4 4 4 9 4 9 9 9 4 9 9 2 

p55:
9600
1 0 0 0 0 0 1 1 1 1 0 1 1 1 1 1 0 1 1 0 
17 18 17 18 18 8 17 17 18 8 17 8 6 8 18 18 8 8 8 12 12 6 12 6 12 12 12 6 6 6 14 14 14 6 6 6 6 6 6 7 7 7 0 7 7 0 0 0 0 0 0 0 7 7 7 7 7 7 7 7 11 11 11 11 11 11 11 7 13 9 9 11 9 11 18 13 9 13 9 9 9 15 15 15 15 15 15 18 15 15 18 18 18 18 18 17 18 18 18 18 

p56:
24550
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 
18 19 2 27 2 12 15 27 22 0 4 28 13 13 28 18 3 20 22 0 11 16 5 24 10 27 27 19 4 2 19 19 4 16 27 6 20 9 24 16 18 9 6 4 8 19 13 21 19 14 24 16 21 21 20 6 11 9 18 25 4 0 7 8 13 11 5 14 28 25 18 12 6 9 23 10 20 23 8 16 23 0 9 25 4 13 4 5 27 7 28 6 25 25 2 3 11 6 0 28 17 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 14 8 26 11 17 19 26 16 2 11 26 17 28 24 12 10 23 9 3 13 28 10 12 22 11 11 25 2 24 21 27 25 24 17 23 0 8 11 2 15 13 13 13 27 10 24 5 27 5 4 3 21 8 20 19 14 26 2 0 10 4 10 5 21 2 6 12 8 28 10 0 21 2 21 12 4 25 12 7 15 10 19 

p57:
30740
1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 0 
18 19 21 27 2 12 21 27 27 28 4 28 13 13 19 18 3 20 22 28 27 16 5 24 10 18 27 19 4 2 19 19 4 16 27 6 20 8 24 16 18 8 6 4 8 19 13 21 19 20 24 16 24 16 8 6 11 26 18 25 4 0 7 8 13 11 5 19 6 25 18 12 19 8 23 23 20 23 8 27 10 0 26 25 4 13 6 5 27 7 11 6 25 25 0 3 11 28 0 28 28 21 12 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 28 13 26 11 24 19 26 16 2 11 26 0 28 24 25 20 5 8 3 3 28 10 12 22 11 11 25 5 24 21 27 7 24 0 23 0 8 11 2 16 13 13 13 27 23 24 5 27 5 4 3 21 5 20 19 10 26 2 0 10 4 23 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 21 10 19 

p58:
48921
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 0 1 1 1 
18 19 2 27 2 12 21 27 18 28 4 28 13 1 28 18 1 20 16 0 11 16 5 24 10 7 27 14 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 2 19 14 24 16 21 21 8 6 11 9 18 25 4 0 7 8 13 25 5 14 6 25 18 12 19 9 23 23 20 23 8 16 10 10 9 25 29 13 4 5 27 7 28 6 25 25 2 1 11 6 0 28 28 21 25 18 4 0 4 24 27 13 19 4 27 12 12 8 28 7 14 8 9 11 28 19 9 16 2 12 19 14 28 24 25 10 23 9 1 13 28 10 12 27 11 11 25 2 24 16 27 25 24 0 23 0 8 11 2 16 13 13 1 24 10 24 5 27 5 4 1 21 1 20 19 20 4 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 25 12 7 21 10 19 

p59:
35904
1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 
18 6 21 27 2 12 21 27 22 27 4 19 10 13 28 18 13 20 22 0 27 16 5 24 10 11 27 19 4 21 19 4 4 16 27 19 20 8 24 16 18 9 6 26 8 19 13 21 19 26 27 16 24 16 8 6 11 9 18 25 4 0 25 8 13 12 5 17 19 12 18 12 6 8 10 23 20 23 8 16 10 0 9 25 4 13 6 5 27 25 28 6 25 25 0 13 11 6 0 28 10 21 25 18 4 0 4 24 22 20 19 4 27 12 12 8 11 25 17 8 9 11 17 19 26 16 2 11 26 17 11 24 25 20 23 9 13 13 28 10 11 22 28 25 25 5 24 21 27 25 24 17 23 0 8 11 2 16 13 13 13 27 13 24 5 27 5 4 13 21 5 20 19 20 26 2 0 20 4 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 25 12 18 21 10 19 

p60:
24663
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
18 19 21 27 2 12 15 28 22 17 4 28 13 1 28 18 1 20 22 28 18 16 5 24 10 18 27 19 29 21 19 19 4 16 27 6 20 8 24 16 18 9 6 26 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 17 28 25 18 12 19 9 23 23 20 23 8 24 23 0 9 25 29 13 4 2 27 7 28 6 25 25 2 13 11 6 0 28 28 15 12 18 4 0 4 24 22 13 19 4 18 12 12 8 28 7 17 8 9 11 17 19 26 16 2 11 14 17 28 21 11 10 23 9 1 13 28 10 12 22 11 11 25 2 24 15 27 25 24 17 23 0 8 11 5 16 13 13 13 27 10 2 5 27 5 29 1 21 1 8 19 14 26 2 0 10 29 10 5 15 21 19 12 9 28 23 0 21 2 21 6 4 25 12 7 21 10 19 

p61:
31979
1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 
18 19 21 27 2 12 15 27 22 17 4 17 10 13 28 18 3 20 22 28 18 21 5 24 10 18 27 19 29 2 19 19 26 21 27 6 20 8 24 15 18 9 6 26 8 19 13 21 19 20 0 24 24 21 8 6 11 9 18 7 29 0 7 8 13 11 5 17 28 25 18 12 19 9 23 23 20 23 8 24 23 0 9 25 29 13 4 2 27 7 28 6 25 25 2 3 28 6 0 28 28 15 12 18 4 0 4 24 22 3 19 4 18 12 12 8 28 7 17 8 26 11 17 19 26 24 2 11 19 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 5 15 3 13 13 27 10 24 5 27 5 29 3 21 5 20 19 20 26 2 0 10 29 10 5 15 2 19 12 8 28 23 0 21 2 21 6 4 25 12 7 21 10 19 

p62:
51028
1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
18 19 2 27 2 12 21 27 22 28 4 28 13 3 28 18 3 20 22 0 18 16 5 24 10 18 27 28 29 2 26 19 26 16 27 6 20 8 24 16 18 9 6 26 8 19 13 21 19 20 24 16 2 16 8 6 11 9 18 25 29 0 7 8 13 11 23 19 28 25 18 12 6 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 21 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 21 28 26 10 28 24 25 20 23 8 3 3 28 10 12 22 11 11 25 2 24 21 27 25 24 17 23 0 8 11 2 16 3 13 13 27 10 24 5 27 5 4 3 21 5 20 28 10 26 0 24 10 29 10 5 21 2 28 12 9 28 23 17 21 2 21 6 4 7 12 25 21 10 19 

p63:
37762
1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
18 19 21 27 2 12 21 27 22 28 4 28 13 3 28 18 3 20 22 0 18 16 5 24 10 18 27 28 29 2 26 19 19 16 27 6 20 8 24 16 18 9 6 26 8 19 13 21 19 20 24 16 2 16 8 6 18 9 18 25 29 0 7 8 13 11 23 19 28 25 18 12 6 9 23 23 20 23 8 16 10 0 9 25 29 20 19 5 27 7 28 6 25 25 2 3 11 6 0 28 28 21 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 21 11 26 10 28 24 25 20 23 9 3 3 28 10 12 22 28 11 25 2 24 21 27 25 24 17 23 0 8 11 2 16 3 13 13 27 10 24 5 27 5 4 3 21 5 8 6 20 26 0 24 10 29 10 5 21 2 28 12 9 28 23 17 24 2 21 6 4 7 12 25 21 10 19 

p64:
24000
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 
18 6 2 27 2 12 15 27 22 28 4 28 13 3 28 18 3 20 22 0 18 16 5 24 10 18 27 14 29 2 28 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 2 16 8 6 25 9 18 25 29 0 7 8 13 11 5 14 28 25 18 12 6 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 28 0 28 28 15 12 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 9 11 17 19 9 16 2 11 19 0 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 2 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 23 20 19 14 4 5 0 10 29 10 5 21 2 6 12 20 28 23 0 21 2 21 6 4 7 12 25 15 10 19 

p65:
31581
1 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
18 19 2 27 2 12 21 27 22 28 4 28 13 3 28 18 3 20 22 0 18 16 5 24 23 18 24 28 29 2 26 19 19 16 27 6 20 8 24 16 18 9 6 26 8 19 13 21 19 20 24 16 24 16 8 6 25 9 18 25 29 0 18 8 13 11 23 19 28 25 18 12 6 9 23 23 20 23 20 16 10 0 9 25 29 20 19 5 27 25 28 6 25 25 2 3 28 6 0 28 28 21 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 25 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 28 11 25 2 24 21 27 25 24 17 23 0 8 11 2 16 3 13 13 27 10 2 5 27 5 4 3 21 5 8 19 10 26 0 24 10 29 10 5 21 2 28 12 9 28 23 17 21 2 21 6 4 25 12 25 21 10 19 

p66:
47431
1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 0 1 1 1 
18 19 21 27 5 12 21 27 18 28 4 28 13 13 28 18 3 20 27 0 18 21 5 24 10 18 27 28 29 2 19 19 4 21 27 6 20 8 24 21 18 9 6 4 8 19 13 21 19 10 24 21 24 21 8 6 11 9 18 25 29 0 25 8 13 11 23 17 19 25 18 12 19 9 23 23 20 23 8 24 10 2 9 25 29 13 6 5 27 7 28 6 25 25 5 3 11 6 0 28 28 21 25 18 4 0 4 24 24 3 19 4 27 12 12 8 28 7 17 8 9 11 17 19 9 2 2 11 4 17 27 24 11 20 23 9 3 3 28 10 12 27 11 11 25 5 21 21 27 25 24 17 23 0 8 11 2 21 3 13 13 27 10 24 5 27 5 4 3 21 5 20 19 10 4 2 0 10 29 10 5 21 2 19 12 8 28 23 0 2 2 21 6 4 7 12 7 21 10 19 

p67:
36247
1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 
18 19 21 22 2 12 21 27 22 28 4 28 13 13 28 18 3 20 22 0 18 16 5 24 10 18 27 19 4 2 19 19 4 16 27 6 20 8 24 16 18 8 6 26 8 19 13 21 19 10 0 16 24 16 8 6 11 8 18 25 4 0 25 8 13 11 23 17 28 25 7 12 19 20 23 23 13 23 8 16 10 0 26 25 4 13 19 5 27 7 28 6 25 25 2 3 11 6 17 28 28 21 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 11 21 11 20 23 8 3 3 28 10 12 22 11 11 25 5 2 16 27 25 24 17 23 0 20 11 2 21 3 13 13 27 10 24 5 27 5 4 3 21 5 20 19 10 26 2 0 10 4 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 21 10 19 

p68:
23533
1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 0 
18 19 21 27 2 12 15 27 18 28 4 28 13 13 28 18 3 20 27 0 18 16 5 24 10 18 24 19 4 2 19 19 4 16 27 6 10 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 25 4 0 25 8 13 11 23 14 6 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 4 13 6 5 27 25 28 6 25 25 2 3 11 12 0 28 28 15 25 18 4 0 4 24 16 3 19 4 27 12 12 8 28 25 14 20 26 11 28 19 26 16 2 11 26 0 28 24 25 20 23 9 3 3 28 14 12 27 12 12 25 5 24 15 27 25 24 28 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 5 20 19 10 26 2 0 10 4 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 18 25 25 15 10 19 

p69:
31596
1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 
18 19 21 27 2 12 15 27 22 28 4 28 10 1 28 18 1 20 27 27 18 16 23 24 10 18 27 19 29 2 19 4 4 16 27 6 20 8 24 16 18 9 6 29 8 19 8 21 19 20 24 16 24 21 8 6 11 9 22 11 29 0 18 8 8 11 23 14 28 11 18 12 19 9 23 23 10 23 8 16 10 0 8 25 29 10 6 2 27 7 28 19 7 25 2 1 28 6 0 28 28 15 25 18 4 0 4 24 22 1 19 4 27 6 12 8 28 7 10 8 19 11 28 19 9 16 2 11 19 0 28 24 25 20 23 9 1 8 28 10 12 22 12 25 25 2 24 15 27 25 24 0 23 0 8 11 2 15 8 8 1 27 10 24 23 27 23 29 1 21 1 20 19 14 4 2 27 10 29 20 2 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19 

p70:
48181
1 1 1 0 1 0 1 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 
18 6 21 27 2 12 15 27 22 28 4 28 13 1 19 18 1 20 22 28 18 16 23 24 10 18 27 19 4 2 19 19 26 16 27 6 8 8 24 16 18 8 6 4 8 19 13 21 19 20 24 16 2 16 8 12 11 8 18 12 4 0 7 8 13 11 23 28 28 25 18 12 19 26 23 23 20 23 8 24 10 0 26 25 4 13 6 2 27 7 28 6 25 25 0 1 11 12 0 28 28 15 25 18 4 0 4 27 22 8 19 4 27 12 11 8 11 7 28 8 26 11 0 19 26 16 2 11 26 0 11 24 25 20 23 8 1 13 28 20 12 22 11 28 25 2 24 21 27 25 24 28 23 0 8 11 2 15 8 13 13 27 10 27 2 27 23 4 1 21 23 20 19 10 26 2 0 20 4 10 2 21 2 6 12 8 11 10 0 21 2 21 6 4 7 6 7 15 10 19 

p71:
36649
1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 
18 19 21 27 2 12 15 27 22 28 4 28 10 1 28 18 1 20 27 27 18 16 23 24 10 18 27 19 29 2 19 4 4 16 27 6 20 8 24 16 18 9 6 29 8 19 8 21 19 20 24 16 24 21 8 6 11 9 22 11 29 0 18 8 8 11 23 14 28 11 18 12 19 9 23 23 10 23 8 16 10 0 8 25 29 10 6 2 27 7 28 19 7 25 2 1 28 6 0 28 28 15 25 18 4 0 4 24 22 1 19 4 27 6 12 8 28 7 10 8 19 11 28 19 9 16 2 11 19 0 28 24 25 20 23 9 1 8 28 10 12 22 12 25 25 2 24 15 27 25 24 0 23 0 8 11 2 15 8 8 1 27 10 24 23 27 23 29 1 21 1 20 19 14 4 2 27 10 29 20 2 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19

小结:

贪心一开始是想按设施来选择较优解, 写完跑出来才发现并不行, 于是换了一个方向; 模拟退火的话, 退火部分比较容易写, 难就难在生成初始解和解的局部搜索部分, 很容易写错然后结果还能算成负数… 不过跑出来结果还是挺好的, 但是离最优差多少就不知道了.

代码:

贪心算法:

主程序: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include "greedy.hpp"

int main() {
    int d = 0;
    cout << "input the number of instances you want to test: (1-71)" << endl;
    cin >> d;
    d = d>71?71:d;
    d = d<1?1:d;
    for (int i = 1; i <= d; ++i) {
        cout << i << ":\n";
        Greedy* greedy = new Greedy(to_string(i));
        greedy->run();
        delete greedy;
    }

    return 0;
}

声明头文件: 

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
#ifndef G_H
#define G_H

#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

typedef struct Facility {
    int capacity;
    int cost;
    Facility(int c = 0, int o = 0)
    :capacity(c),cost(o){}
} Facility;

typedef struct Customer {
    int demand;
    vector<int> cost;
    Customer(int d = 0, vector<int> c = vector<int>())
    :demand(d), cost(c){}
    Customer(float d = 0.)
    :demand((int)d){}
} Customer;

typedef struct Solution {
    int cost;
    vector<int> status;
    vector<int> assignment;
    Solution(int c = 0):cost(c){}
};

class Greedy {
public:
    Greedy() = default;
    ~Greedy() = default;
    Greedy(string _dataset):dataset(_dataset){};
    void initial();
    void run();
    void readInstance();
    void initialSolution();
    void sortFacilitiesCost();
    void greedySelect();
    bool itakein(int customer, int facility);
    void result();
    void cal();
    void swapV(vector<int>&, int, int);
private:
    string dataset;
    int customerCount, facilityCount;
    vector<Facility> facilities, orginF;
    // sort index
    vector<vector<int>> ceffective;
    vector<int> cindex;
    vector<Customer> customers;
    Solution solution;
    clock_t start,end;
    int realResult, displayInput;
};

#endif

实现文件: 

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
#include "greedy.hpp"

void Greedy::initial() {
    this->realResult = 0;
    this->displayInput = 0;
    srand(time(0));
}

void Greedy::run() {
    this->initial();
    this->readInstance();
    this->start = clock();
    this->initialSolution();
    this->sortFacilitiesCost();
    this->greedySelect();
    this->end = clock();
    this->result();
}

void Greedy::readInstance() {
    string path = "./Instances/p";
    path += dataset;
    fstream file;
    file.open(path);
    file >> this->facilityCount >> this->customerCount;
    if (this->displayInput == 10) {
        cout << path << endl;
        cout << this->facilityCount << " " << this->customerCount << endl;
    }
    for (int i = 0; i < this->facilityCount; ++i) {
        int f, c;
        file >> f >> c;
        if (this->displayInput == 10) {
            cout << f << " " << c << endl;
        }
        this->facilities.push_back(Facility(f, c));
    }
    int j = 0;
    for (int i = 0; i < this->customerCount; ++i) {
        float d;
        file >> d;
        this->customers.push_back(Customer(d));
        if (this->displayInput == 10) {
            cout << d << " ";
            if (++j >= 10) {
                cout << endl;
                j = 0;
            }
        }
    }
    for (int i = 0; i < this->facilityCount; ++i) {
        if (this->displayInput == 10) {
            cout << i << ": ";
        }
        for (int j = 0; j < this->customerCount; ++j) {
            float c;
            file >> c;
            if (this->displayInput == 10) {
                cout << c << " ";
            }
            this->customers[j].cost.push_back((int)c);
        }
        if (this->displayInput == 10) {
            cout << endl;
        }
    }
    this->orginF = this->facilities;
    file.close();
}

void Greedy::result() {
    if (this->displayInput == 1) {
        cal();
    }
    string path = "./result_greedy/p";
    path += dataset;
    ofstream file(path);
    file << endl << "p" << dataset << ":\n";
    file << this->solution.cost << endl;

    cout << "cost: " << this->solution.cost << endl;
    cout << "time: " << (double)(this->end - this->start)/CLOCKS_PER_SEC << endl;
    for (int i = 0; i < this->solution.status.size(); ++i) {
        file << this->solution.status[i] << ' ';
    }
    file << endl;
    for (int i = 0; i < this->solution.assignment.size(); ++i) {
        file << this->solution.assignment[i] << ' ';
    }
    file << endl;
    if (this->displayInput == 1) {
        file << this->realResult;
    }
    file.close();
}

void Greedy::cal() {
    for (int i = 0; i < this->solution.status.size(); ++i) {
        this->realResult += this->solution.status[i] * this->orginF[i].cost;
    }
    for (int i = 0; i < this->customers.size(); ++i) {
        this->realResult += this->customers[i].cost[this->solution.assignment[i]];
    }
}

void Greedy::initialSolution() {
    this->solution.cost = 0;
    this->solution.status.clear();
    this->solution.assignment.clear();
    for (int i = 0; i < this->facilityCount; ++i) {
        this->solution.status.push_back(0);
    }
    for (int i = 0; i < this->customerCount; ++i) {
        this->solution.assignment.push_back(-1);
    }
}

void Greedy::sortFacilitiesCost() {
    for (int i = 0; i < this->customerCount; ++i) {
        vector<int> index;
        for (int j = 0; j < this->facilityCount; ++j) {
            index.push_back(j);
        }
        for (int x = 0; x < this->facilityCount-1; ++x) {
            for (int y = x+1; y < this->facilityCount; ++y) {
                if (this->customers[i].cost[index[x]] > this->customers[i].cost[index[y]]) {
                    this->swapV(index, x, y);
                }
            }
        }
        this->ceffective.push_back(index);
        this->cindex.push_back(i);
    }

    for (int i = 0; i < this->customerCount-1; ++i) {
        for (int j = i+1; j < this->customerCount; ++j) {
            if (this->customers[this->cindex[i]].cost[this->ceffective[this->cindex[i]][0]]/1.0
                /this->customers[this->cindex[i]].cost[this->ceffective[this->cindex[i]][2]]
                > this->customers[this->cindex[j]].cost[this->ceffective[this->cindex[j]][0]]/1.0
                /this->customers[this->cindex[j]].cost[this->ceffective[this->cindex[j]][2]]
                )
            {
                this->swapV(this->cindex, i, j);
            }
        }
    }

    if (this->displayInput == 1)
    {
        for (int i = 0; i < this->customerCount; ++i)
        {
            for (int j = 0; j < this->facilityCount; ++j)
            {
                cout << this->customers[this->cindex[i]].cost[this->ceffective[this->cindex[i]][j]] << ", ";
            }
            cout << endl;
        }
    }
}

void Greedy::greedySelect() {
    for (int i = 0; i < this->customerCount; ++i)
    {
        int canPut = 0;
        while (!this->itakein(this->cindex[i], this->ceffective[this->cindex[i]][canPut])) {
            canPut++;
            if (canPut >= this->facilityCount) {
                break;
            }
        }
    }
}

bool Greedy::itakein(int customer, int facility) {
    if (this->facilities[facility].capacity < this->customers[customer].demand) {
        return false;
    }
    this->facilities[facility].capacity -= this->customers[customer].demand;
    this->solution.cost += this->customers[customer].cost[facility];
    this->solution.assignment[customer] = facility;
    if (this->solution.status[facility] == 0) {
        this->solution.status[facility] = 1;
        this->solution.cost += this->facilities[facility].cost;
    }
    return true;
}

void Greedy::swapV(vector<int>& a, int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}
模拟退火:

主程序: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include "SA.hpp"

int main() {
    int d = 0;
    cout << "input the number of instances you want to test: (1-71)" << endl;
    cin >> d;
    d = d>71?71:d;
    d = d<1?1:d;
    for (int i = 1; i <= d; ++i) {
        // cout << i << ":\n";
        cout << "|" << i << "|";
        SA* sa = new SA(to_string(i));
        sa->run();
        delete sa;
    }

    return 0;
}

声明头文件: 

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
#ifndef SA_H
#define SA_H

#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

typedef struct Facility {
    int capacity;
    int cost;
    Facility(int c = 0, int o = 0)
    :capacity(c),cost(o){}
} Facility;

typedef struct Customer {
    int demand;
    vector<int> cost;
    Customer(int d = 0, vector<int> c = vector<int>())
    :demand(d), cost(c){}
    Customer(float d = 0.)
    :demand((int)d){}
} Customer;

typedef struct Solution {
    int cost;
    vector<int> status;
    vector<int> assignment;
    Solution(int c = 0):cost(c){}
};

class SA {
public:
    SA() = default;
    ~SA() = default;
    SA(string _dataset):dataset(_dataset){};
    void initial();
    void run();
    void readInstance();
    void generateInitialSolution();
    bool checkSolutionValid();
    void SimulatedAnnealing();
    void generateNewSolution();
    double probability(int x);
    void takeout(int customer);
    bool takein(int customer, int facility);
    bool itakein(int customer, int facility);
    void result();
    void cal();
private:
    string dataset;
    int customerCount, facilityCount;
    vector<Facility> facilities, nfacilities, orginF, minF;
    vector<Customer> customers;
    Solution solution, ns, mins;
    double T, T_min, arate;
    int loop;
    clock_t start,end;
    int realResult, displayInput;
};

#endif

实现文件: 

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
#include "SA.hpp"

void SA::initial() {
    this->loop = 200;
    this->T = 100.0;
    this->T_min = 0.0001;
    this->arate = 0.96;
    this->realResult = 0;
    this->displayInput = 0;
    srand(time(0));
}

void SA::run() {
    this->initial();
    this->readInstance();
    int t = this->facilityCount*this->customerCount/5;
    this->loop = t>200?t:200;
    this->start = clock();
    this->generateInitialSolution();
    this->SimulatedAnnealing();
    this->end = clock();
    this->result();
}

void SA::readInstance() {
    string path = "./Instances/p";
    path += dataset;
    fstream file;
    file.open(path);
    file >> this->facilityCount >> this->customerCount;
    if (this->displayInput == 1) {
        cout << path << endl;
        cout << this->facilityCount << " " << this->customerCount << endl;
    }
    for (int i = 0; i < this->facilityCount; ++i) {
        int f, c;
        file >> f >> c;
        if (this->displayInput == 1) {
            cout << f << " " << c << endl;
        }
        this->facilities.push_back(Facility(f, c));
    }
    int j = 0;
    for (int i = 0; i < this->customerCount; ++i) {
        float d;
        file >> d;
        this->customers.push_back(Customer(d));
        if (this->displayInput == 1) {
            cout << d << " ";
            if (++j >= 10) {
                cout << endl;
                j = 0;
            }
        }
    }
    for (int i = 0; i < this->facilityCount; ++i) {
        if (this->displayInput == 1) {
            cout << i << ": ";
        }
        for (int j = 0; j < this->customerCount; ++j) {
            float c;
            file >> c;
            if (this->displayInput == 1) {
                cout << c << " ";
            }
            this->customers[j].cost.push_back((int)c);
        }
        if (this->displayInput == 1) {
            cout << endl;
        }
    }
    this->orginF = this->facilities;
    file.close();
}

void SA::result() {
    if (this->displayInput == 1) {
        cal();
    }
    string path = "./result/p";
    path += dataset;
    ofstream file(path);
    // file.open(path);
    file << endl << "p" << dataset << ":\n";
    file << this->solution.cost << endl;

    // cout << "cost: " << this->solution.cost << endl;
    // cout << "time: " << (double)(this->end - this->start)/CLOCKS_PER_SEC << endl;
    cout << "" << this->solution.cost;
    cout << "|" << (double)(this->end - this->start)/CLOCKS_PER_SEC << "|";
    cout << endl;
    for (int i = 0; i < this->solution.status.size(); ++i) {
        file << this->solution.status[i] << ' ';
    }
    file << endl;
    for (int i = 0; i < this->solution.assignment.size(); ++i) {
        file << this->solution.assignment[i] << ' ';
    }
    file << endl;
    if (this->displayInput == 1) {
        file << this->realResult;
    }
    file.close();
    if (this->displayInput == 1) {
        cout << "min cost: " << this->mins.cost << endl;
    }
}

void SA::cal() {
    for (int i = 0; i < this->solution.status.size(); ++i) {
        this->realResult += this->solution.status[i] * this->orginF[i].cost;
    }
    for (int i = 0; i < this->customers.size(); ++i) {
        this->realResult += this->customers[i].cost[this->solution.assignment[i]];
    }
}

void SA::generateInitialSolution() {
    this->solution.cost = 0;
    this->solution.status.clear();
    this->solution.assignment.clear();
    for (int i = 0; i < this->facilityCount; ++i) {
        this->solution.status.push_back(0);
    }
    for (int i = 0; i < this->customerCount; ++i) {
        this->solution.assignment.push_back(0);
    }
    for (int i = 0; i < this->customerCount; ++i) {
        int go = rand()%this->facilityCount;
        while (! this->itakein(i, go)) {
            go = rand()%this->facilityCount;
        }
    }
    this->mins = this->solution;
    this->minF = this->facilities;
}

void SA::SimulatedAnnealing() {
    while (this->T > this->T_min) {
        for (int i = 0; i < this->loop; ++i) {
            this->generateNewSolution();
            if (this->ns.cost < this->mins.cost) {
                this->mins = this->ns;
                this->minF = this->nfacilities;
            }
            if (this->ns.cost < this->solution.cost) {
                this->solution = this->ns;
                this->facilities = this->nfacilities;
            } else if (this->probability(this->ns.cost - this->solution.cost) 
                        >= (double)(rand()%1000)/1000.0) {
                this->solution = this->ns;
                this->facilities = this->nfacilities;
            }
        }
        this->T *= this->arate;
    }
    this->solution = this->mins;
    this->facilities = this->minF;
    for (int i = 0; i < this->loop; ++i) {
        this->generateNewSolution();
        if (this->ns.cost < this->solution.cost) {
            this->solution = this->ns;
            this->facilities = this->nfacilities;
        }
    }
}

void SA::generateNewSolution() {
    this->nfacilities = this->facilities;
    this->ns = this->solution;
    int randomx = rand()%4;
    // 随机安排两个顾客到随机两个设施
    // if (true) {
    if (randomx == 0) {
        // a顾客拿出来
        int a = rand()%this->customerCount;
        this->takeout(a);
        // b顾客拿出来
        int b = rand()%this->customerCount;
        while (a == b) {
            b = rand()%this->customerCount;
        }
        this->takeout(b);
        // 将a顾客放入c
        int c = rand()%this->facilityCount;
        while (this->nfacilities[c].capacity < this->customers[a].demand) {
            c = rand()%this->facilityCount;
        }
        this->takein(a, c);
        // 将b顾客放入d
        int d = rand()%this->facilityCount;
        while (this->nfacilities[d].capacity < this->customers[b].demand) {
            d = rand()%this->facilityCount;
        }
        this->takein(b, d);
    } else if (randomx == 1) { // 随机选出三个顾客, 进行循环左移
        while (true) {
            int a = rand()%this->customerCount;
            int b = rand()%this->customerCount;
            int c = rand()%this->customerCount;
            while (a == b) {
                b = rand()%this->customerCount;
            }
            while (c == a || b == c) {
                c = rand()%this->customerCount;
            }
            int afrom = this->ns.assignment[a], bfrom = this->ns.assignment[b],
                cfrom = this->ns.assignment[c];
            // 拿出a
            this->takeout(a);
            // 拿出b
            this->takeout(b);
            // 拿出c
            this->takeout(c);
            // 尝试放入
            if (this->takein(a, cfrom)) {
                if (this->takein(b, afrom)) {
                    if (this->takein(c, bfrom)) {
                        break;
                    } else {
                        this->takeout(a);
                        this->takeout(b);
                    }
                } else {
                    this->takeout(a);
                }
            }
            this->takein(a, afrom);
            this->takein(b, bfrom);
            this->takein(c, cfrom);
        }
    } else if (randomx == 2) { //随机将一个顾客随机放到一个设施
        // a顾客拿出来
        int a = rand()%this->customerCount;
        int old = this->solution.assignment[a];
        this->takeout(a);
        
        // 将a顾客放入c
        int c = rand()%this->facilityCount;
        while (this->nfacilities[c].capacity < this->customers[a].demand || c == old) {
            c = rand()%this->facilityCount;
        }
        this->takein(a, c);
    } else { // 随机两个顾客交换设施
        while (true) {
            int a = rand()%this->customerCount;
            int b = rand()%this->customerCount;
            while (a == b) {
                b = rand()%this->customerCount;
            }
            int afrom = this->ns.assignment[a], bfrom = this->ns.assignment[b];
            // 拿出a
            this->takeout(a);
            // 拿出b
            this->takeout(b);
            // 尝试放入
            if (this->takein(a, bfrom)) {
                if (this->takein(b, afrom)) {
                    break;
                } else {
                    this->takeout(a);
                }
            }
            this->takein(a, afrom);
            this->takein(b, bfrom);
        }
    }
}

double SA::probability(int x) {
    return 1./(1 + pow(2.7182818284, (double)x/T));
}

void SA::takeout(int customer) {
    int from = this->ns.assignment[customer];
    this->nfacilities[from].capacity += this->customers[customer].demand;
    this->ns.cost -= this->customers[customer].cost[from];
    if (this->nfacilities[from].capacity == this->orginF[from].capacity) {
        this->ns.status[from] = 0;
        this->ns.cost -= this->nfacilities[from].cost;
    }
}

bool SA::takein(int customer, int facility) {
    if (this->nfacilities[facility].capacity < this->customers[customer].demand) {
        return false;
    }
    this->nfacilities[facility].capacity -= this->customers[customer].demand;
    this->ns.cost += this->customers[customer].cost[facility];
    this->ns.assignment[customer] = facility;
    if (this->ns.status[facility] == 0) {
        this->ns.status[facility] = 1;
        this->ns.cost += this->nfacilities[facility].cost;
    }
    return true;
}

bool SA::itakein(int customer, int facility) {
    if (this->facilities[facility].capacity < this->customers[customer].demand) {
        return false;
    }
    this->facilities[facility].capacity -= this->customers[customer].demand;
    this->solution.cost += this->customers[customer].cost[facility];
    this->solution.assignment[customer] = facility;
    if (this->solution.status[facility] == 0) {
        this->solution.status[facility] = 1;
        this->solution.cost += this->facilities[facility].cost;
    }
    return true;
}