10.15
Idea. Let p[i] be the given price of a piece of length i.
Define r[j] = best revenue for a rod of length j.
The optimal revenue for length j is either the un-cut price p[j] or a first cut of length i (1 ≤ i < j) plus the best revenue of the remaining j–i inches:
[math]\displaystyle{ r[j]=\max_{1\le i\le j}\bigl(p[i]+r[j-i]\bigr),\qquad r[0]=0 }[/math]
Computing r[1] … r[n] bottom-up fills each entry in O(n) time, giving total time O(n2) and O(n) space.
Algorithm (Python 3).
def cut_rod(price): # price[0] unused; price[i] = p[i]
n = len(price) - 1 # rod length
r = [0]*(n+1) # best revenues
cut = [0]*(n+1) # arg-max for reconstruction
for j in range(1, n+1):
best = -1
for i in range(1, j+1):
val = price[i] + r[j-i]
if val > best:
best, cut[j] = val, i
r[j] = best
# optional: rebuild solution
pieces = []
k = n
while k > 0:
pieces.append(cut[k])
k -= cut[k]
return r[n], pieces # (max value, list of cuts)
Example.
For the table in the prompt, cut_rod returns (22, [2, 6]), i.e. cut the 8-inch rod into pieces 2 + 6 to obtain the maximum value 22.
Back to
Chapter 10
