-
Notifications
You must be signed in to change notification settings - Fork 0
/
solve_e.py
139 lines (122 loc) · 4.64 KB
/
solve_e.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
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
from utils import parseINPUT
from utils import generateSubmission, judgeFunction
from utils import bubbleSortReversedByvalue, orderedLib2N_n
import copy
import numpy as np
consider_range = 2
sum_depth = 0
max_prob = 0.5
np.random.seed(0)
def solve(B_value: list, sum_value: dict, candidate_lib: list, N_number: list,
curDay: int, depth: int):
def get_lib_value(lib):
number = min(N_numberCur[lib], (D - curDay - T[lib]) * M[lib])
if number >= N_numberCur[lib]:
return sum_valueCur[lib]
else:
sum = 0
time = 0
for book in N[lib]:
if time >= number:
break
if B_valueCur[book] != 0:
time += 1
sum += B_valueCur[book]
return sum
def average_value(lib):
return get_lib_value(lib) / T[lib]
def reduce_sum_value(sumvalue_list, choosed_lib, B_valueList,
N_numberlist):
number = min(N_numberCur[choosed_lib],
(D - curDay - T[choosed_lib]) * M[choosed_lib])
time = 0
for book in N[choosed_lib]:
if time >= number:
break
if B_valueList[book] != 0:
time += 1
for lib in book_dic[book]:
sumvalue_list[lib] -= B_valueList[book]
N_numberlist[lib] -= 1
B_valueList[book] = 0
orderedLib = []
Sum_gain = 0
B_valueCur = copy.deepcopy(B_value)
sum_valueCur = copy.deepcopy(sum_value)
N_numberCur = copy.deepcopy(N_number)
# iteration begans
while curDay < D:
# get the best lib
value = list(map(average_value, candidate_lib))
# bubbleSortReversed(candidate_lib, cmp, consider_range)
curLib = -1
gain = 0
if depth >= 1 and curDay >= 0:
bubbleSortReversedByvalue(candidate_lib, value, consider_range)
max_value = 0
for lib in candidate_lib[:consider_range]:
temp_B_value = copy.deepcopy(B_valueCur)
temp_sum_value = copy.deepcopy(sum_valueCur)
temp_candidate_lib = copy.deepcopy(candidate_lib)
temp_N_number = copy.deepcopy(N_numberCur)
curgain = get_lib_value(lib)
temp_candidate_lib.remove(lib)
reduce_sum_value(temp_sum_value, lib, temp_B_value,
temp_N_number)
_, est_gain = solve(temp_B_value, temp_sum_value,
temp_candidate_lib, temp_N_number,
curDay + T[lib], depth - 1)
est_sumgain = curgain + est_gain
if est_sumgain >= max_value:
max_value = est_sumgain
curLib = lib
gain = curgain
else:
bubbleSortReversedByvalue(candidate_lib, value, consider_range)
prob = np.random.rand(1)
if prob < max_prob:
choose_index = 1
else:
choose_index = 0
curLib = candidate_lib[choose_index]
gain = int(value[choose_index] * T[curLib])
reduce_sum_value(sum_valueCur, curLib, B_valueCur, N_numberCur)
Sum_gain += gain
candidate_lib.remove(curLib)
# if depth == sum_depth:
# print(("curDay : %d") % curDay)
curDay += T[curLib]
if curDay < D:
orderedLib.append(curLib)
return orderedLib, Sum_gain
if __name__ == "__main__":
def sortedByvalue(book):
return B_value[book]
input = parseINPUT("e_so_many_books.txt")
B, L, D, B_value, N, T, M, N_n = input.values()
book_dic = {}
for i in range(L):
for book in N[i]:
if book in book_dic:
book_dic[book].append(i)
else:
book_dic[book] = [i]
sumValue = {}
for lib in range(L):
value = 0
for book in N[lib]:
value += B_value[book]
sumValue[lib] = value
for lib in N:
lib.sort(key=sortedByvalue, reverse=True)
orderedLib, Sum_gain = solve(B_value, sumValue, [i for i in range(L)], N_n,
0, sum_depth)
shippedBooks = orderedLib2N_n(orderedLib, B_value, T, M, N_n, N, D)
submission = generateSubmission(orderedLib, shippedBooks)
print(Sum_gain)
print(judgeFunction(submission, B_value))
# # # write submission to file.
# # with open(
# # "f_answer_est_range_%d_depth_%d_threshday_%d.txt" %
# # (consider_range, sum_depth, thresh_day), "w") as f:
# # f.write(submission)