Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Understanding the bottom-up rod cut implementation

In Introduction to Algorithms(CLRS), Cormen et al. talk about solving the Rod-cutting problem as follows(page 369)

EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
    let r[0...n] and s[0....n] be new arrays
    r[0] = 0

    for j = 1 to n:
        q = -infinity   

        for i = 1 to j:
            if q < p[i] + r[j - i]:  // (6)
                q = p[i] + r[j - i]
                s[j] = i
        r[j] = q

    return r and s

Here p[i] is the price of cutting the rod at length i, r[i] is the revenue of cutting the rod at length i and s[i], gives us the optimal size for the first piece to cut off.

My question is about the outer loop that iterates j from 1 to n and the inner loop i that goes from 1 to n as well.

On line 6 we are comparing q (the maximum revenue gained so far) with r[j - i], the maximum revenue gained during the previous cut.

When j = 1 and i = 1, it seems to be fine, but the very next iteration of the inner loop where j = 1 and i = 2, won't r[j - i] be r[1 - 2] = r[-1]?

I am not sure if the negative index makes sense here. Is that a typo in CLRS or I am missing something here?

I case some of you don't know what the rod-cutting problem is, here's an example.

like image 471
sc_ray Avatar asked Mar 31 '11 22:03

sc_ray


People also ask

How do you solve a rod cutting problem?

The problem can be solved by calculating the maximum attainable value of rod by cutting in various pieces in a bottom up fashion by first calculating for smaller value of n and then using these values to calculate higher values of n. The time complexity of this solution is O(n^2).

What is the maximum value that you can get after cutting the rod and selling the pieces?

Explanation: Brute force, Dynamic programming and Recursion can be used to solve the rod cutting problem. What is the maximum value that you can get after cutting the rod and selling the pieces? Explanation: The pieces {1,2 2} give the maximum value of 12. Sanfoundry Certification Contest of the Month is Live.

What is DP method?

The dynamic programming (DP) method is used to determine the target of freshwater consumed in the process. DP is generally used to reduce a complex problem with many variables into a series of optimization problems with one variable in every stage. It is characterized fundamentally in terms of stages and states.

What is Rod cutting problem in dynamic programming?

Algorithms Dynamic Programming (DP) The problem statement is quite simple, given a rod of some length 'n' and the price associated with each piece of the rod, the rod has to be cut and sold. The process of cutting should be in such a way that the amount(revenue) obtained from selling is maximum.


1 Answers

Here's the key: for i = 1 to j

i will begin at 1 and increase in value up to but not exceeding the value of j.

i will never be greater than j, thus j-i will never be less than zero.

like image 181
Unsigned Avatar answered Oct 12 '22 23:10

Unsigned