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.
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).
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.
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.
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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With