Dynamic Programming - Rod Cutting Bottom Up Algorithm (CLRS) Solution Incorrect?

Question

For the "rod cutting" problem:

Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces. [link]

Introduction to Algorithms (CLRS) page 366 gives this pseudocode for a bottom-up (dynamic programming) approach:

1. BOTTOM-UP-CUT-ROD(p, n)              
2. let r[0 to n]be a new array .        
3. r[0] = 0                             
4. for j = 1 to n                       
5.     q = -infinity                    
6.     for i = 1 to j                   
7.         q = max(q, p[i] + r[j - i])  
8.     r[j] = q                         
9. return r[n]

Now, I'm having trouble understanding the logic behind line 6. Why are they doing max(q, p[i] + r[j - i]) instead of max(q, r[i] + r[j - i])? Since, this is a bottom up approach, we'll compute r[1] first and then r[2], r[3]... so on. This means while computing r[x] we are guaranteed to have r[x - 1].

r[x] denotes the max value we can get for a rod of length x (after cutting it up to maximize profit) whereas p[x] denotes the price of a single piece of rod of length x. Lines 3 - 8 are computing the value r[j] for j = 1 to n and lines 5 - 6 are computing the maximum price we can sell a rod of length j for by considering all the possible cuts. So, how does it ever make sense to use p[i] instead of r[i] in line 6. If trying to find the max price for a rod after we cut it at length = i, shouldn't we add the prices of r[i] and r[j - 1]?

I've used this logic to write a Java code and it seems to give the correct output for a number of test cases I've tried. Am I missing some cases in which where my code produces incorrect / inefficient solutions? Please help me out. Thanks!

class Solution {
    private static int cost(int[] prices, int n) {
        if (n == 0) {
            return 0;
        }

        int[] maxPrice = new int[n];

        for (int i = 0; i < n; i++) {
            maxPrice[i] = -1;
        }

        for (int i = 1; i <= n; i++) {
            int q = Integer.MIN_VALUE;

            if (i <= prices.length) {
                q = prices[i - 1];
            }

            for (int j = i - 1; j >= (n / 2); j--) {
                q = Math.max(q, maxPrice[j - 1] + maxPrice[i - j - 1]);
            }

            maxPrice[i - 1] = q;
        }

        return maxPrice[n - 1];
    }


    public static void main(String[] args) {
       int[] prices = {1, 5, 8, 9, 10, 17, 17, 20};

        System.out.println(cost(prices, 8));
    }
}

Can you please explain what's the "Rod Cutting" problem is ? — Varun Narisetty, Oct 31 '18 at 20:48

score 3 · Accepted Answer · answered Oct 31 '18 at 21:14

They should be equivalent.

The intuition behind the CLRS approach is that they are trying to find the single "last cut", assuming that the last piece of rod has length i and thus has value exactly p[i]. In this formulation, the "last piece" of length i is not cut further, but the remainder of length j-i is.

Your approach considers all splits of the rod into two pieces, where each of the two parts can be cut further. This considers a superset of cases compared to the CLRS approach.

Both approaches are correct and have the same asymptotic complexity. However, I would argue that the CLRS solution is more "canonical" because it more closely matches a common form of DP solution where you only consider the last "thing" (in this case, the last piece of uncut rod).

score 0 · Answer 2 · answered Nov 01 '18 at 16:08

I guess both of the approach are correct.

before we prove both of them are correct lets define what exactly each approach does

p[i] + r[j - i] will give you the max value you can obtain from a rod of length j and of the piece is of size "i"(cannot divide that piece further)

r[i] + r[j-i] will give you the max value you can obtain from a rod of length i and the first cut was made at length "i"(can devide both the pieces further)

Now consider we have a rod of length X and the solution set will contain piece of length k

and since k is 0 < k < X you will find the max value at p[k] + r[X-k] in the first approach

and in the second approach you can find the same result with r[k] + r[X-k] since we know that r[k] will be >= p[k]

But in you approach you can get the result much faster(half of the time) since you are slicing the rod from both ends so in you approach you can run the inner loop for half of the length should be good.

But I think in you code there is a bug in inner for loop it should be j >= (i / 2) instead of j >= (n / 2)

Dynamic Programming - Rod Cutting Bottom Up Algorithm (CLRS) Solution Incorrect?

2 Answers2