Consider a modification of the rod-cutting problem in which, in addition to a pr

Question

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.

(a) Write a recurrence for the solution; pay attention to how sub-problems are addressed.

(b) Write psuedocode for a brute force algorithm based on your recurrence

(c) Write psuedocode for a memoized algorithm based brute force solution

(d) Write psuedocode for a bottom-up dynamic programming solution

Explanation / Answer

Soluion:

// ALGORITHM : recursive dynamic programming algorithm for BOTTOM-UP-CUT-ROD

BOTTOM-UP-CUT-ROD(p,n)
let r[0..n] be a new array
for i = 0 to n
r[i] = -
return MEMOIZED-CUT-ROD-AUX(p,n,r)

MEMOIZED-CUT-ROD-AUX(p,n,r)
If i = n
return r[n]
if i < n
q = 0
else q = -
for i = n
q = max( q, p[i] + MEMOIZED-CUT-ROD-AUX(p,n-1,r))
r[n] = q
return q

The only observation is that no cut can occur in l. 7 if i = n. As long as i < n we have a cut of cost c, to separate the first part from the rest; when i = n there is no rest, thus no cut and no cost.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.