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
|
from utils import get, init_table, print_table
def optimal_itinerary(duration, items):
min_duration = min([duration for duration, _ in items])
max_duration = max([duration for duration, _ in items])
table = init_table(rows=len(items), cols=int(max_duration / min_duration), default=0)
to_index = lambda duration: int(duration / min_duration) - 1
to_duration = lambda i: i * min_duration + min_duration
for row in range(len(table)):
for col in range(len(table[row])):
curr_duration = to_duration(col)
duration, value = items[row]
if duration > curr_duration:
a = 0
else:
a = value + get(table, row - 1, to_index(curr_duration - duration))
b = get(table, row - 1, col)
table[row][col] = max([a, b])
print_table(table)
return table[-1][-1]
# You're in London for two days, and you'd like to see the following
# attractions. How can you maximize your time spent in London?
westminster = (0.5, 7)
globe_theater = (0.5, 6)
national_gallery = (1, 9)
british_museum = (2, 9)
st_pauls_cathedral = (0.5, 8)
items = [
westminster,
globe_theater,
national_gallery,
british_museum,
st_pauls_cathedral,
]
result = optimal_itinerary(2, items)
expected = 24
print(result, expected)
assert result == expected
print("Success!")
|
