From pseudo-code to python
Recursive top-down implementation
p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
def cut_rod(p, n):
if n == 0:
return 0
q = p[0]
for i in range(1, n+1):
q = max(q, p[i] + cut_rod(p, n-i))
return q
res = cut_rod(p, 4)
print(res)
Memoized cut rod
def memoized_cut_rod(p, n):
r = [-1 for _ in range(n + 1)]
return memoized_cut_rod_aux(p, n, r)
def memoized_cut_rod_aux(p, n, r):
if r[n] >= 0:
return r[n]
q = p[0]
if n == 0:
q = 0
else:
for i in range(1, n + 1):
q = max(q, p[i] + memoized_cut_rod_aux(p, n - i, r))
r[n] = q
return q
res = memoized_cut_rod(p, 4)
print(res)
Bottom up cut rod
def bottom_up_cut_rod(p, n):
r = [0 for _ in range(n + 1)]
for j in range(1, n + 1):
q = p[0]
for i in range(1, j + 1):
q = max(q, p[i] + r[j - i])
r[j] = q
return r[n]
res = bottom_up_cut_rod(p, 4)
print(res)
15.1-1
T(n)=2nT(n)=1+n−1∑j=0T(j)Show that equation (15.4) follows from equation (15.3) and the initial condition T(0)=1.
Binomial of one variable refer here T(j) counts the number of calls (including recursive calls) due to the call CUT-ROD. It also means how many ways we can cut the rod.
n−1∑j=0(n−1j)xj=(n−10)x0+(n−11)x1+(n−12)x2+⋯+(n−1j)xn−1=(1+x)n−1Let x=1 so we can get 2n−1
n−1∑j=0(n−1j)1j=2n−1Now we want to run how many ways to cut the rod from 0 until n−1. This recursion tree has 2nnodes
incase I forgot, the sum of power of 2 is a geometric series
n−1∑j=02j=20+21+22+23⋯2n−1=2n−1T(n)=1+n−1∑j=02jT(n)=1+2n−1=2n15.1-2
Show, by means of a counterexample, that the following “greedy” strategy does not always determine an optimal way to cut rods. Define the density of a rod of length i to be pi/i, that is, its value per inch. The greedy strategy for a rod of length n cuts off a first piece of length i, where 1≤i≤n, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length n−i.
15.1-3
Consider a modification of the rod-cutting problem in which, in addition to a price pi for each rod, each cut incurs a fixed cost of c. The revenue associated with a solution is now the sum of the prices of the pieces minus the costs of making the cuts. Give a dynamic-programming algorithm to solve this modified problem.
def bottom_up_cut_rod(p, n, c):
r = [0 for _ in range(n + 1)]
for j in range(1, n + 1):
q = p[0]
for i in range(1, j + 1):
q = max(q, p[i] + r[j - i] - c)
r[j] = q
return r[n]
res = bottom_up_cut_rod(p, 4, 0.5)
print(res)
15.1-4
Modify MEMOIZED-CUT-ROD to return not only the value but the actual solution, too.
15.1-5
The Fibonacci numbers are defined by recurrence (3.22). Give an O(n)-time dynamic programming algorithm to compute the nth Fibonacci number. Draw the subproblem graph. How many vertices and edges are in the graph?
def fibonacci_dynamic(n):
a, b = 0, 1
while n > 0:
a, b = b, a + b
n -= 1
return a
res = fibonacci_dynamic(8)
print(res)