Finding the rod pieces in the rod cut issue

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 o

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

StackExchange Code Review Q#102322, answer score: 3