Rod Cutting Using Dynamic Programming Part 1
Serling Enterprises buys long steel rods and cuts them into shorter rods, which it then sells. Each cut is free. The management of Serling Enterprises wants to know the best way to cut up the rods.
We assume that we know, for i = 1,2,... the price pi in dollars that Serling Enterprises charges for a rod of length i inches. Rod lengths are always an integral number of inches.
Above figure gives us a sample price table.
The rod-cutting problem is the following. Given a rod of length n inches and a table of prices pi for i = 1,2,... n, determine the maximum revenue rn obtainable by cutting up the rod and selling the pieces. Note that if the price pn for a rod of length n is large enough, an optimal solution may require no cutting at all. Consider the case when n = 4.
Above figure shows all the ways to cut up a rod of 4 inches in length, including the way with no cuts at all. We see that cutting a 4-inch rod into two 2-inch pieces produces revenue p2 + p2 = 5 + 5 = 10, which is optimal.
We can cut up a rod of length n in 2n-1 different ways, since we have an independent option of cutting, or not cutting, at distance i inches from the left end.
for i = 1,2,...,n-1. We denote a decomposition into pieces using ordinary additive notation, so that 7 = 2 + 2 + 3 indicates that a rod of length 7 is cut into three pieces—two of length 2 and one of length 3. If an optimal solution cuts the rod into k pieces, for some 1 ≤ k ≤ n, then an optimal decomposition
n = i1 + i2 + ... + ik
of the rod into pieces of lengths i1, i2, ..., ik provides maximum corresponding revenue
r = pi1 + pi2 + ... + pik
For our sample problem, we can determine the optimal revenue figures ri, for i = 1,2,...,10, by inspection, with the corresponding optimal decompositions
r1 = 1 from solution 1 = 1 (no cuts),
r2 = 5 from solution 2 = 2 (no cuts),
r3 = 8 from solution 3 = 3 (no cuts),
r4 = 10 from solution 4 = 2 + 2,
r5 = 13 from solution 5 = 2 + 3,
r6 = 17 from solution 6 = 6 (no cuts),
r7 = 18 from solution 7 = 1 + 6 or 7 = 2 + 2 + 3,
r8 = 22 from solution 8 = 2 + 6,
r9 = 25 from solution 9 = 3 + 6,
r10 = 30 from solution 10 = 10 (no cuts),
More generally, we can frame the values rn for n ≥ 1 in terms of optimal revenues from shorter rods:
rn = max(pn,r1+rn-1,r2+rn-2,...,rn-1+r1)
The first argument, pn , corresponds to making no cuts at all and selling the rod of length n as is. The other n - 1 arguments to max correspond to the maximum revenue obtained by making an initial cut of the rod into two pieces of size i and n - i, for each i = 1,2,...,n-1, and then optimally cutting up those pieces further, obtaining revenues ri and rn-i from those two pieces. Since we don’t know ahead of time which value of i optimizes revenue, we have to consider all possible values for i and pick the one that maximizes revenue. We also have the option of picking no i at all if we can obtain more revenue by selling the rod uncut. Note that to solve the original problem of size n, we solve smaller problems of the same type, but of smaller sizes. Once we make the first cut, we may consider the two pieces as independent instances of the rod-cutting problem. The overall optimal solution incorporates optimal solutions to the two related subproblems, maximizing revenue from each of those two pieces. We say that the rod-cutting problem exhibits optimal substructure: optimal solutions to a problem incorporate optimal solutions to related subproblems, which we may solve independently. In a related, but slightly simpler, way to arrange a recursive structure for the rod- cutting problem, we view a decomposition as consisting of a first piece of length i cut off the left-hand end, and then a right-hand remainder of length n - i. Only the remainder, and not the first piece, may be further divided. We may view every decomposition of a length-n rod in this way: as a first piece followed by some decomposition of the remainder. When doing so, we can couch the solution with no cuts at all as saying that the first piece has size i = n and revenue pn and that the remainder has size 0 with corresponding revenue r0 = 0. We thus obtain the following simpler version of equation:
rn = max(pi,rn-i) ∀ 1 ≤ i ≤ n
In this formulation, an optimal solution embodies the solution to only one related subproblem—the remainder—rather than two.
The following procedure implements the computation implicit in equation ( rn = max(pi,rn-i) ∀ 1 ≤ i ≤ n )in a straightforward, top-down, recursive manner.
CUT-ROD(p,n)
if n == 0
return 0
q = -infinity
for i = 1 to n
q = max(q,p[i] + CUT-ROD(p,n-i))
return q// C++ Code
int CUT_ROD(int prices[],int n){
if(n <= 0){
return 0;
}
int q = INT_MIN;
for(int i = 0;i < n;i++){
q = max(q,prices[i] + CUT_ROD(prices,n-i-1));
}
return q;
}Procedure CUT-ROD takes as input an array p[1..n] of prices and an integer n, and it returns the maximum revenue possible for a rod of length n. If n = 0, no revenue is possible, and so CUT-ROD returns 0. Initializes the maximum revenue q to -infinity, so that the loop correctly computes q = max(q,p[i]+CUT-ROD(p,n-i)) ∀ 1≤i≤n then returns the value. A simple induction on n proves that this answer is equal to the desired answer rn.
If you were to code up CUT-ROD in your favorite programming language and run it on your computer, you would find that once the input size becomes moderately large, your program would take a long time to run. For n = 40, you would find that your program takes at least several minutes, and most likely more than an hour. In fact, you would find that each time you increase n by 1, your program’s running time would approximately double.
Why is CUT-ROD so inefficient? The problem is that CUT-ROD calls itself recursively over and over again with the same parameter values; it solves the same subproblems repeatedly.
Above figure illustrates what happens for n = 4, CUT-ROD(p,n) calls CUT-ROD(p,n) for i = 1,2,...,n. Equivalently, CUT-ROD(p,n) calls CUT-ROD(p,j) for each j = 0,1,2,...,n-1. When this process unfolds recursively, the amount of work done, as a function of n, grows explosively.
To analyze the running time of CUT-ROD , let T(n) denote the total number of calls made to CUT-ROD when called with its second parameter equal to n. This expression equals the number of nodes in a subtree whose root is labeled n in the recursion tree. The count includes the initial call at its root. Thus, T(0) = 1 and
The initial 1 is for the call at the root, and the term T(j) counts the number of calls (including recursive calls) due to the call CUT-ROD(p,n-i), where j = n - i.
First question would be In how many ways a cut can be made ?
In a rod of size n, 1 cut can be made in (n-1)C(1) ways n choose k
2 cuts = (n-2)C(2) and 3 cuts = (n-3)C(3) and so on
k cuts = (n-k)C(k)
ways to do 1 cut + ways to do 2 cuts + ….. ways to do k cuts ..+ ways to do n-1 cuts
Can we do better ?
YES, We can. We will discuss the Dyanmic Programming Solution for Rod Cutting in next gist where we will use Recursions with Memoization.
Chapter 15 Dynamic Programming. Introduction to Algorithms, 3rd Edition by Cormen, Leiserson, Rivest & Stein (CLRS)
UMass Lowell Computer Science 91.503 - Analysis of Algorithms