15.1-3
# when c=2
def BOTTOM_UP_CUT_ROD(p, n, c):
r = [0] * (n+1)
for i in range(1, n+1):
q = p[i]
for j in range(1, i):
q = max(q, p[j] + r[i-j] - c)
r[i] = q
return r[n]
def main():
p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
c = 2
print('when cost c = 2: \n')
for i in range(1, len(p)):
print('the max profit of n = %i is: ' %i, BOTTOM_UP_CUT_ROD(p, i, c))
main()
Output-1
15.1-4
def MEMOIZED_CUT_ROD_AUX(p, n, r, s):
if r[n] >= 0:
return r[n], s
if n == 0:
q = 0
else:
q = -1
for i in range(1, n+1):
temp_q, temp_s = MEMOIZED_CUT_ROD_AUX(p, n-i, r, s)
if q < temp_q + p[i]:
q = temp_q + p[i]
s = temp_s
s[n] = i
r[n] = q
return q, s
def MEMOIZED_CUT_ROD(p, n):
r = [-1] * (n+1)
s = [0] * (n+1)
return MEMOIZED_CUT_ROD_AUX(p, n, r, s)
def PRINT_CUT_ROD_SOLUTION(p, n):
r_nth, s = MEMOIZED_CUT_ROD(p, n)
print('the max profit of n = %i is: %i' %(n,r_nth))
print('the sulution of max profit is: ', end = '')
while n > 0:
print(s[n], end = '\t')
n = n - s[n]
def main():
p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
for i in range(1, len(p)):
PRINT_CUT_ROD_SOLUTION(p, i)
print('\n')
main()
Output-2
15.1-5
def fibonacci(n):
f = [0] * (n+1)
f[0] = 0
f[1] = 1
for i in range(2, n+1):
f[i] = f[i-1] + f[i-2]
return f[n]
def main():
n = 6
print('the %ith of fibonacci sequence is: ' %n, fibonacci(n))
main()
Output-3
