Finding the rod pieces in the rod cut issue

Question

I have been reading the chapter 15 of "Introduction to Algorithms" (3rd edition) by Cormen, etc. The chapter 15 is about dynamic programming, and the first example they show us is the "rod cut problem".

Now, I have spent some time trying to understand it, but mostly trying to understand the pseudocode, and why it really works. I think dynamic programming is probably the most difficult design technique to put in practice that I have seen so far. The ideas are quite easy, but applying them is quite a nightmare, at least for me. You can choose between memoisation or a bottom-up approach, but you need to have a clear and deep understanding of the problem, and usually this requires quite a lot of time, but if you are in an exam...

From now on, I will assume that you know what the rod cut problem is.

Now, I wanted to create, based on a pseudocode from the book, an algorithm for the rod cutting problem that actually returns a list of the indices where we can find the small pieces that we have used to maximise the total price.

I have used Python, which simplifies quite a lot the process of writing programs, in general.

The following is the algorithm that I came up with (which is really similar to the pseudo code that the authors provide to find the maximum revenue for a rod of a certain length, but that algorithm does not calculate and returns which smaller pieces maximise the revenue):

def extended_bottom_up_rod_cut(prices, n):
    revenues = [-sys.maxsize] * (n + 1)

    s = [[]] * (n + 1)

    revenues[0] = 0
    s[0] = [0]

    for i in range(1, n + 1):

        max_revenue = -sys.maxsize  # a big small number

        for j in range(1, i + 1):

            # Note that j + (i - j) = i.
            # What does this mean, or why should this fact be useful?
            # Note that at each iteration of the outer loop,
            # we are trying to find the max_revenue for a rod of length i
            # (and we want also to find which items we are including to obtain that max_revenue).
            # To obtain a rod of size i, we need at least 2 other smaller rods,
            # unless we do not cut the rod.
            # Now, to obtain a rod of length i,
            # we need to put together a rod of length j < i and a rod of length i - j < j,
            # because j + (i - j) = i, as we stated at the beginning.
            if max_revenue < prices[j] + revenues[i - j]:

                max_revenue = prices[j] + revenues[i - j]

                if prices[i - j] != 0:
                    s[i] = [j, i - j]  # Indices of prices such that price[j] + price[i - j] = max_revenue of i
                else:
                    s[i] = [j]

        revenues[i] = max_revenue

    return revenues, s

First of all, is the algorithm correct?

Apparently, it seems that it returns the right answer, but I am a bit confused: as the size of the rod increases, we are always going to just use at most 2 small pieces, and no more than that, but why such an algorithm should give the right answer? Why using 3 or more pieces would not give the right answer?

Answer 1

I don't get this part of the code:

            if prices[i - j] != 0:
                s[i] = [j, i - j]  # Indices of prices such that price[j] + price[i - j] = max_revenue of i
            else:
                s[i] = [j]

Why not just use have s just store the best size, e.g.:

            s[i] = j

To get the list of parts for a certain size rod, just use:

def best_rod_parts(s, n):
  parts = []
  while n > 0:
    parts.append( s[n] )
    n = n - s[n]
  return parts

where s is the array returned from your solving procedure.

Here is how I would write it:

def solve(prices, n):
    revenue = [0] * (n+1)  # can assume price >= 0
    size = [0] * (n+1)     # best length to cut

    for i in range(1,n+1):
      bestRev, bestSize = 0, 0  # best solution so far

      for j in range(1,i+1):
        rev = price[j] + revenue[i-j]
        if rev > bestRev:
          bestRev = rev
          bestSize = j
      revenue[i] = bestRev
      size[i] = bestSize

If you want s to contain the list of pieces, then you should modify the code this way:

def solve(prices, n):
  revenue = [0] * (n+1)
  sizes = [ [] ] * (n+1)

  for i in range(1,n+1):
    bestRev, bestSize = 0,0
    for j in range (1,i+1):
      rev = prices[j] + revenue[i-j]
      if rev > bestRev:
        bestRev = rev
        bestSize = j
    sizes[i] = sizes[i-bestSize] + [bestSize]
  return revenue, sizes

Answer 2

I found a counter example where my code fails to calculate the list of small rod pieces that are used to maximise the revenue.

Suppose I have the following list:

p1 = [0, 1, 5, 2, 9, 10]

(0 is there just to fill the position 0).

Now, if I have a rod of length 5, whose price is 10, the best way to maximise its revenue is by cutting it in two pieces of length 2, plus a piece of length 1. In fact, this results in a revenue of 11.

Other ways such as:

• A piece of length 5 (no cut at all) gives a revenue of 10

• Cutting it in 2 pieces, one of length 2 and one of length 3, would give us a revenue of 7.

  Note that the actual revenue for a rod of length 3 is 6 (a rod of length 1 + a rod of length 2), and 6 + 5 (5 from a rod of length 2) would also give us the optimal solution, but note that this is the solution that my new algorithm also picks, but using a rod of length 4 (which picks 2 rods of length 2) + a rod of length 1.

• Cutting it in 5 pieces of length 1, would give us a revenue of 5.

• Cutting it in 2 pieces, one of length 1 and one of length 4, would give us a revenue of 10. This is actually where my algorithm calculates the best revenue. It checks what is the best revenue for a rod of length 4, which is to use 2 rods of length 2, which results in a revenue of 10 for a rod of length 4.

would result in a smaller revenue.

The problem with my code is that with i - j I am not referring to the list indices already calculated for previous smaller subproblems, instead I am just including them as if the element at position i - j gives me directly the solution, but this is not true for all cases, because what gives me the solution is the revenue of i - j and not the element itself. To fix my code, I just need to refer to the already calculated list of indices whenever I use a revenue[i - j].

Here's the complete code:

def extended_bottom_up_rod_cut(prices, n):
    revenues = [-sys.maxsize] * (n + 1)
    s = [[]] * (n + 1)

    revenues[0] = 0
    s[0] = [0]

    for i in range(1, n + 1):

        max_revenue = -sys.maxsize

        for j in range(1, i + 1):

            if max_revenue < prices[j] + revenues[i - j]:

                max_revenue = prices[j] + revenues[i - j]

                if revenues[i - j] != 0:
                    s[i] = [j] + s[i - j]
                else:
                    s[i] = [j]

        revenues[i] = max_revenue

    return revenues, s