Rod Cutting Problem (Confusion about price and revenue)

Question

If you are familiar with the rod cutting algorithm, the question is at the bottom.

In the following algorithm (C++ code), rev is the array containing the maximum revenue a rod of given length could have, while the price array is for the standard price without cutting the rod into further pieces. The algorithm given below is what I am finding from many sources to find the maximum revenue of a rod of length n.

    int cutRod(int price[], int n) 
    { 
       int rev[n+1]; 
       rev[0] = 0; 
       int i, j; 
       for (i = 1; i<=n; i++) 
       { 
           int max_val = INT_MIN; 
           for (j = 0; j < i; j++) 
              max_val = max(max_val, price[j] + rev[i-j-1]); 
           val[i] = max_val; 
       } 
       return val[n]; 
    }

As can be seen, this algorithm works by cutting the rod into two pieces where one piece is not cut further (we consider its price) while the other piece may be cut (we consider its revenue). This means we would need to do this for n times considering different lengths to cut.

QUESTION: Why can't we have this loop run half the number of iterations by passing only revenue of both the pieces rather than one price and one revenue, because revenue holds the information about whether the price is maximum if the rod is cut or if it is not cut? Wouldn't that be more efficient? Simply put: price[1]<=rev[1], price[2]<=rev[2], ... So for rod of length n=3, instead of finding the maximum out of: price[1]+rev[2], price[2]+rev[1], price[3]+rev[0] (n elements) we could just find the maximum of: rev[1]+rev[2],rev[3]+rev[0] (⌊n/2⌋ + 1 elements)

You're doing for (i = 1; i<=n; i++), which, if n is the length/size of price, means that you're skipping the first element and going one beyond the end of the array. Did you mean for (i = 0; i<n; i++) instead? Or, if you want to skip the first element: for (i = 1; i<n; i++)? — Craig Estey
@CraigEstey: It can be done either way to consider the option that the rod was not cut (that is, it is cut at length 0 or at length n) — N. Paramahamsan

btilly btilly · Accepted Answer · 2020-03-23T18:39:10

Yes, you can implement this by copying prices to the revenue array (takes O(n)) and then only looking at the revenue of splits into size i+j where i<j. And should get a factor of 2 speed increase.

But it also makes the logic more complicated, which gets in the way of using this as a simple demonstration problem for dynamic programming. The point isn't to find the factor of 2 algorithmic improvement, but instead to improve the big-O.

Secondly the problem has many variants. In the one you were looking at, there is a price for every length of rod. But what if you have prices for some lengths but not others? (For example the USA sells nails in lengths specified in 1/4" increments, but as https://www.homedepot.com/c/ab/types-of-nails/9ba683603be9fa5395fab909c451e98 shows, we only sell some lengths of nail.) The simpler problem generalizes better.

Rod Cutting Problem (Confusion about price and revenue)

1 Answers