-
Notifications
You must be signed in to change notification settings - Fork 3
/
dp_tickets.py
60 lines (49 loc) · 1.45 KB
/
dp_tickets.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
### This is the code to use dynamical programming to solve problem 1 in HW2 for CSE 6140
D, W, M = 2, 7, 20
days = [0,1,1,0,0,1,0,1,1,1,1,1,1,1,0,0,0,0,0,1,1,0,1,1,0,0,1,1,1,1,0,0]
Memo = [0]*len(days)
def f(i):
if Memo[i] == 0:
if days[i] == 0 and i > 0:
Memo[i] = f(i-1)
else:
if i <= 0:
return 0
else:
minfee = min(f(i-1) + D, f(i-7) + W, f(i-30) + M)
Memo[i] = minfee
return Memo[i]
f(len(days)-1)
print(Memo)
Memo = [0]*len(days)
def g(i):
if i <= 0:
return 0
if Memo[i] == 0:
if days[i] == 0:
Memo[i] = g(i-1)
else:
Memo[i] = min(g(i-1) + D, g(i-7) + W, g(i-30) + M)
return Memo[i]
g(len(days)-1)
print(Memo)
def print_message(i, d):
print('Buy a $' + str(d) + ' dolloar ticket on day ', i)
def find_solution(i):
if i<= 0:
return
if days[i] == 1:
if Memo[i] == Memo[max(0, i-1)] + D:
print_message(max(1, i), D)
find_solution(i-1)
if Memo[i] == Memo[max(0, i-7)] + W:
print_message(max(1, i-6), W)
find_solution(i-7)
if Memo[i] == Memo[max(0, i - 30)] + M:
print_message(max(1, i - 29), M)
find_solution(i - 30)
else:
find_solution(i-1)
day = 29
print('The minimum fee George needs to pay for the first ', day, 'days are', Memo[day])
find_solution(day)