CODEWITHSUNDEEP
algorithmdynamic-programmingclrs
PM_ME_PUZZLES
PM_ME_PUZZLES

Reputation: 11

Result calculation in rod cutting

I am learning the rod cutting algorithm from CLRS book.

I believe I understand the logic and my below solution was accepted on this OJ.

#include <climits>
#include <iostream>

using namespace std;

int prices[101];
int result[101];

int function(int length)
{

    if (length == 0)
        return 0;    

    if (result[length] != INT_MIN)
    {
        return result[length];
    }

    //calculate result for length
    //if cutting the rod is more profitable, this variable will get overwritten in the loop below
    int current_max = prices[length];

    for (int cut_size = 1; cut_size < length; cut_size++)
    {
        int a;
        int b;
        a = function(cut_size);     //this question is about this step
        b = function(length - cut_size);
        if (a + b > current_max)
            current_max = a + b;
    }
    result[length] = current_max;
    return current_max;
}

int main() {

    int number_of_test_cases;
    int length_of_rod;

    cin>>number_of_test_cases;

    while (number_of_test_cases--)
    {
        cin>>length_of_rod;

        for (int i = 1; i <= length_of_rod; i++)
        {
            cin>>prices[i];
            result[i] = INT_MIN;
        }

        //profit of cutting rod to size 1
        result[1] = prices[1];

        cout<<function(length_of_rod)<<endl;
    }
    return 0;
}

Above, I have implemented the logic as explained in the book, except with a little modification which is what this post is about.

From the book,

1: let r[0..n] be a new array
2: r[0] = 0
3: for j = 1 to n
4:    q = -1
5:    for i = 1 to j
6:       q = max(q, p[i] + r[j-i])
7:    r[j] = q
8: return r[n]

p is the input array containing the profits for rod length going from 1 to n, and r is for storing the results.

Why on line 6 here is r[i] not being used instead of p[i], when r[i] already contains the best price that rod of length i can be sold for? It is possible that r[i] contains a higher value than p[i], implying that a rod of length i can fetch a higher price after being cut instead of being sold apiece. Of course, for the last run of the loop when i = j and the rod of length j is not being cut, it has to be p[i], because r[j] is the value that is being calculated and it doesn't exist yet. But i am confused about the other runs of the loop when the rod is being cut.

My solution uses the logic q = max(q, r[i] + r[j-i]) through these statements - 

a = function(cut_size);
b = function(length - cut_size);
if (a + b > current_max)
    current_max = a + b;

If i modify it with a = prices[cut_size] according to the book, it is still successful on the OJ.

What am i missing here?

Upvotes: 0

Views: 66

Answers (1)

xashru
xashru

Reputation: 3600

Consider i to be the length of the last piece you have cut (there is always going to be one, if you don't do any cut then the whole rod is the last piece). Since its a single piece, the profit you gain from this is p[i]. So what this approach is doing is trying for all possible last cut and using one that maximizes value.

Upvotes: 1

Related Questions