6
\$\begingroup\$

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?

\$\endgroup\$
3
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You can find the explanation of why I am using the code you didn't understand in the comments just above the if statement. Basically, when we update max_revenue, we know which elements we have lastly used, that is the ones at positions j and i - j. The part if prices[i - j] != 0: is just not to included the redundant price for 0 pieces, which is unnecessary. \$\endgroup\$ – nbro Aug 30 '15 at 22:08
  • \$\begingroup\$ For the first solution you are giving using a while loop, it is quite similar to the one given by the authors, which actually just return the first best piece (?)... \$\endgroup\$ – nbro Aug 30 '15 at 22:12
  • \$\begingroup\$ Anyway, I think my solution is wrong, but maybe I found why... \$\endgroup\$ – nbro Aug 30 '15 at 22:15
  • \$\begingroup\$ For my first solution, s[j] is just the best size of the first piece to cut for a rod of size j. To find all of the sizes you need to use the while loop. \$\endgroup\$ – ErikR Aug 30 '15 at 22:20
  • \$\begingroup\$ Found a mistake - setting sizes should be sizes[i] = sizes[i - bestSize] + [bestSize] \$\endgroup\$ – ErikR Aug 31 '15 at 14:50
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I still don't understand why you are checking if prices[i-j] != 0 .... Just always use s[i] = [j] + s[i-j]. Can you come up with a case where you need that check? \$\endgroup\$ – ErikR Aug 31 '15 at 13:22
  • \$\begingroup\$ Your program gives incorrect results on this input: extended_bottom_up_rod_cut([0, 10, 0, 0, 0, 0, 0 ], 4) The revenue array is correct, but the sizes array isn't. \$\endgroup\$ – ErikR Aug 31 '15 at 13:34
  • \$\begingroup\$ The sizes array isn't because we both copied it from the book! My program fails because there's a typo. It is not prices[i - j] but revenues[i - j] in that part that you don't understand. I will edit the answer. \$\endgroup\$ – nbro Aug 31 '15 at 14:40
  • \$\begingroup\$ The check if revenues[i - j] != 0: is important because I don't want to include the index for a rod of revenue 0. \$\endgroup\$ – nbro Aug 31 '15 at 14:49
  • \$\begingroup\$ So I did have a typo in my code. See my second solution. I still don't understand, though, why you need to check if revenues[i-j] != 0. It's totally unnecessary. \$\endgroup\$ – ErikR Aug 31 '15 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.