Rod Cutting Using Dynamic Programming Part 2

Rod Cutting Part 2.md

Rod Cutting Using Dynamic Programming Part 2

Serling Enterprises buys long steel rods and cuts them into shorter rods, which it then sells. Each cut is free. The management of Serling Enterprises wants to know the best way to cut up the rods.

Part 1

Rod Cutting Using Dynamic Programming Part 1

We will now discuss how to convert CUT-ROD into an efficient algorithm, using dynamic programming.

The dynamic-programming method works as follows. Having observed that a naive recursive solution ( we discussed in part 1) is inefficient because it solves the same subproblems repeatedly, we arrange for each subproblem to be solved only once, saving its solution. If we need to refer to this subproblem’s solution again later, we can just look it up, rather than recompute it. Dynamic programming thus uses additional memory to save computation time; it serves an example of a time-memory trade-off. The savings may be dramatic: an exponential-time solution may be transformed into a polynomial-time solution. A dynamic-programming approach runs in polynomial time when the number of distinct subproblems involved is polynomial in the input size and we can solve each such subproblem in polynomial time.

There are usually two equivalent ways to implement a dynamic-programming approach. We shall illustrate both of them with our rod-cutting example.

The first approach is top-down with memoization. (NOTE: MEMOIZATION != MEMORIZATION) In this approach, we write the procedure recursively in a natural manner, but modified to save the result of each subproblem (usually in an array or hash table). The procedure now first checks to see whether it has previously solved this subproblem. If so, it returns the saved value, saving further computation at this level; if not, the procedure computes the value in the usual manner. We say that the recursive procedure has been memoized; it “remembers” what results it has computed previously.

The second approach is the bottom-up method. This approach typically depends on some natural notion of the “size” of a subproblem, such that solving any particular subproblem depends only on solving “smaller” subproblems. We sort the subproblems by size and solve them in size order, smallest first. When solving a particular subproblem, we have already solved all of the smaller subproblems its solution depends upon, and we have saved their solutions. We solve each subproblem only once, and when we first see it, we have already solved all of its prerequisite subproblems.

These two approaches yield algorithms with the same asymptotic running time, except in unusual circumstances where the top-down approach does not actually recurse to examine all possible subproblems. The bottom-up approach often has much better constant factors, since it has less overhead for procedure calls. Here is the the pseudocode for the top-down CUT-ROD procedure, with memoization added:

MEMOIZED-CUT-ROD(p,n)
    let r[0..n] be a new array
    for i = 0 to n
        r[i] = - infinity
    return MEMOIZED-CUT-ROD-AUX(p,n,r)

int MEMOIZED_CUT_ROD(int p[],int n){
    int r[n+1];
    for(int i = 0;i<n+1;i++){
        r[i] = INT_MIN;
    }
    return MEMOIZED_CUT_ROD_AUX(p,n,r);
}

MEMOIZED-CUT-ROD-AUX(p,n,r)
    if r[n] ≥ 0
        return r[n]
    if n == 0
        q = 0
    else 
        q = - infinity
        for i = 1 to n
            q = max(q,p[i] + MEMOIZED-CUT-ROD-AUX( p, n-i, r ) )
    r[n] = q
    return q

// C++ Code
int MEMOIZED_CUT_ROD_AUX(int p[],int n,int r[]){
    if(r[n] >= 0){ return r[n]; }
    int q;
    if(n == 0){ q = 0; }
    else{
        q = INT_MIN;
        for(int i=0;i<n;i++){
            q = max(q,p[i] + MEMOIZED_CUT_ROD_AUX(p,n-i-1,r));
        }
    }
    r[n] = q;
    return q;
}

Here, the main procedure MEMOIZED-CUT-ROD initializes a new auxiliary array r[0..n] with the value -infinity, a convenient choice with which to denote “unknown.” (Known revenue values are always nonnegative.) It then calls its helper routine, MEMOIZED-CUT-ROD-AUX.

The procedure MEMOIZED-CUT-ROD-AUX is just the memoized version of our previous procedure, CUT-ROD. It first checks to see whether the desired value is already known and, if it is, then returns it. Otherwise, compute the desired value q in the usual manner, saves it in r[n], and returns it.

The bottom-up version is even simpler:

BOTTOM-UP-CUT-ROD(p,n)
    let r[n] be a new array
    r[0] = 0
    for j = 1 to n
        q = -infinity
        for i = 1 to j
            q = max(q,p[i] + r[j-i])
        r[j] = q
    return r[n]

// C++ Code
int BOTTOM_UP_CUT_ROD(int p[],int n){
    int r[n+1];
    int q;
    r[0] = 0;
    for (int j = 1; j <= n; j++)
    {
        q = INT_MIN;
        for (int i = 0; i < j; i++)
        {
            q = max(q,p[i]+r[j-i-1]);
        }
        r[j] = q;
    }
    return r[n];
}

Time Complexity

Both algorithms BOTTOM-UP-CUT-ROD and MEMOIZED-CUT-ROD take linear time to solve for each value of n, so total time complexity is θ(n²)

Reconstructing a Solution

If we are interested in the set of cuts for an optimal solution as well as the revenue it generates, just keep track of the choice made to optimize each subproblem, we can do this by adding a second array s, which keeps track of the optimal size of the first piece cut in each subproblem.

Extended-Bottom-Up-Cut-Rod(p,n,r,s)
    let r & s be a new array of size 0,...,n
    r[0] = 0 and s[0] = 0
    for j = 1 to n do
        q = -infinity
        for i = 1 to j do
            if q < p[i] + r[j-i]
                q = p[i] + r[j-i]
                s[j] = i
        r[j] = n
    end
    return r,s

// C++ Code
int Extended_Bottom_Up_Cut_Rod(int p[],int n,int r[],int s[]){
    int q;
    r[0] = 0;s[0] = 0;
    for (int j = 1; j < n+1; j++)
    {
        q = INT_MIN;
        for (int i = 0; i < j; i++)
        {
            if(q < (p[i] + r[j-i-1])){
                q = p[i] + r[j-i-1];
                s[j] = i;
            }
        }
        r[j] = q;
    }
    return q;
}

Print-Cut-Rod-Solution(s,n,r)
    while n > 0 do
    print s[n]
    n = n - s[n]

// C++ Code
void Print_Cut_Rod_Soution(int s[],int n,int r[]){
    int j = n-1;
    while(j > 0){
        cout<<"cut(s) : "<<s[j]<<", max obtainable profit is "<<r[s[j]]<<endl;
        j = j - s[n-1];
    }
}

CLRS Problem 15.1-4 & 15.1-5

Modify MEMOIZED-CUT-ROD to return not only the value but the actual solution, too

MODIFIED-CUT-ROD(p, n)
    let r[0..n] and s[0..n] be new arrays
    for i = 0 to n
        r[i] = -∞
    (val, s) = MODIFIED-CUT-ROD-AUX(p, n, r, s)
    print "The optimal value is" val "and the cuts are at"
    j = n
    while j > 0
        print s[j]
        j = j - s[j]

// C++ Code
int MODIFIED_CUT_ROD(int p[],int n){
    int r[n+1];int s[n+1];
    for (int i = 0; i < n+1; i++){
        r[i] = INT_MIN;
    }
    int val = MODIFIED_CUT_ROD_AUX(p,n,r,s);
    int j = n;
    while (j > 0){
        cout<<s[j];
        j = j - s[n];
    }
}

MODIFIED-CUT-ROD-AUX(p, n, r, s)
    if r[n] ≥ 0
        return r[n]
    if n == 0
        q = 0
    else q = -∞
        for i = 1 to n
            (val, s) = MODIFIED-CUT-ROD-AUX(p, n - i, r, s)
            if q < p[i] + val
                q = p[i] + val
                s[n] = i
    r[n] = q
    return (q, s)

// C++ Code
int MODIFIED_CUT_ROD_AUX(int p[],int n,int r[],int s[]){
    int q;
    if(r[n] > 0){ return r[n]; }
    if(n == 0) { q = 0; }
    else{
        q = INT_MIN;
        for (int i = 0; i < n; i++)
        {
            int val = MODIFIED_CUT_ROD_AUX(p,n-i-1,r,s);
            if(q < (p[i] + val)){
                q = p[i] + val;
                s[n] = i;
            }
        }
    }
    r[n] = q;
    return q;
}

CITATIONS

Chapter 15 Dynamic Programming. Introduction to Algorithms, 3rd Edition by Cormen, Leiserson, Rivest & Stein (CLRS)

Dynamic Programming for the confused : Rod cutting problem

UMass Lowell Computer Science 91.503 - Analysis of Algorithms

University of Nebraska-Lincoln ( Computer Science & Engineering 423/823 Design and Analysis of Algorithms )

rod_cutting.md

#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;

void cout_arr(int a[],int n){
    for(int i=0;i<n;i++){
        cout<<"\t"<<a[i];
        if(i==n-1){
            cout<<endl;
        }
    }
}

void cout_r(int r[],int n){
    for(int i=0;i<n;i++){
        cout<<"\t"<<r[i];
        if(i==n-1){
            cout<<endl;
        }
    }
}

void cout_s(int r[],int n){
    for(int i=0;i<n;i++){
        int x = i > 0 ? r[i]+1 : 0;
        cout<<"\t"<<x;
        if(i==n-1){
            cout<<endl;
        }
    }
}

// Naive Simple Approach
int CUT_ROD(int p[],int n){
    if(n <= 0){
        return 0;
    }
    int q = INT_MIN;
    for(int i=0;i<n;i++){
        q = max(q,p[i] + CUT_ROD(p,n-i-1));
    }
    return q;
}

int MEMOIZED_CUT_ROD_AUX(int p[],int n,int r[]){
    if(r[n] >= 0){ return r[n]; }
    int q;
    if(n == 0){ q = 0; }
    else{
        q = INT_MIN;
        for(int i=0;i<n;i++){
            q = max(q,p[i] + MEMOIZED_CUT_ROD_AUX(p,n-i-1,r));
        }
    }
    r[n] = q;
    return q;
}

int MEMOIZED_CUT_ROD(int p[],int n){
    int r[n+1];
    for(int i = 0;i<n+1;i++){
        r[i] = INT_MIN;
    }
    return MEMOIZED_CUT_ROD_AUX(p,n,r);
}

int BOTTOM_UP_CUT_ROD(int p[],int n){
    int r[n+1];
    int q;
    r[0] = 0;
    for (int j = 1; j <= n; j++)
    {
        q = INT_MIN;
        for (int i = 0; i < j; i++)
        {
            q = max(q,p[i]+r[j-i-1]);
        }
        r[j] = q;
    }
    return r[n];
}

int Extended_Bottom_Up_Cut_Rod(int p[],int n,int r[],int s[]){
    int q;
    r[0] = 0;s[0] = 0;
    for (int j = 1; j < n+1; j++)
    {
        q = INT_MIN;
        for (int i = 0; i < j; i++)
        {
            if(q < (p[i] + r[j-i-1])){
                q = p[i] + r[j-i-1];
                s[j] = i;
            }
        }
        r[j] = q;
    }
    return q;
}

void Print_Cut_Rod_Soution(int s[],int n,int r[]){
    int j = n-1;
    while(j > 0){
        cout<<"cut(s) : "<<s[j]<<", max obtainable profit is "<<r[s[j]]<<endl;
        j = j - s[n-1];
    }
}

int MODIFIED_CUT_ROD_AUX(int p[],int n,int r[],int s[]){
    int q;
    if(r[n] > 0){ return r[n]; }
    if(n == 0) { q = 0; }
    else{
        q = INT_MIN;
        for (int i = 0; i < n; i++)
        {
            int val = MODIFIED_CUT_ROD_AUX(p,n-i-1,r,s);
            if(q < (p[i] + val)){
                q = p[i] + val;
                s[n] = i;
            }
        }
    }
    r[n] = q;
    return q;
}

int MODIFIED_CUT_ROD(int p[],int n){
    int r[n+1];int s[n+1];
    for (int i = 0; i < n+1; i++){
        r[i] = INT_MIN;
    }
    auto start = high_resolution_clock::now();
    int val = MODIFIED_CUT_ROD_AUX(p,n,r,s);
    auto stop = high_resolution_clock::now(); 
    auto duration = duration_cast<microseconds>(stop - start);
    cout<<"Using MODIFIED_CUT_ROD function, Maximum Obtainable Revenue is "<<val<<" and the cuts are at: "<<endl;
    int j = n;
    while (j > 0){
        cout<<"length of "<<s[j]<<", price is $"<<r[s[j]]<<endl;
        j = j - s[n];
    }
    cout << "Time taken function: "<< duration.count() << " microseconds" << endl<<endl;

}



int main(int argc, char const *argv[])
{
    int p[] = {2,7,10,14,19,22,23,26,28,29};
    int n = 10;
    cout<<"For n = "<<n<<endl;

    auto start = high_resolution_clock::now(); 
    int result = CUT_ROD(p,n);
    auto stop = high_resolution_clock::now(); 
    auto duration = duration_cast<microseconds>(stop - start);
    cout<<"Using Naive CUT_ROD function, Maximum Obtainable Revenue is "<<result<<endl;
    cout << "Time taken function: "<< duration.count() << " microseconds" << endl<<endl;

    start = high_resolution_clock::now(); 
    result = MEMOIZED_CUT_ROD(p,n);
    stop = high_resolution_clock::now(); 
    duration = duration_cast<microseconds>(stop - start);
    cout<<"Using MEMOIZED_CUT_ROD function, Maximum Obtainable Revenue is "<<result<<endl;
    cout << "Time taken by function: "<< duration.count() << " microseconds" << endl<<endl;

    start = high_resolution_clock::now(); 
    result = BOTTOM_UP_CUT_ROD(p,n);
    stop = high_resolution_clock::now(); 
    duration = duration_cast<microseconds>(stop - start);
    cout<<"Using BOTTOM_UP_CUT_ROD function, Maximum Obtainable Revenue is "<<result<<endl;
    cout << "Time taken function: "<< duration.count() << " microseconds" << endl<<endl;
    
    

    int r[n+1];
    int s[n+1];
    start = high_resolution_clock::now(); 
    int ebucr_r = Extended_Bottom_Up_Cut_Rod(p,n,r,s);
    stop = high_resolution_clock::now(); 
    duration = duration_cast<microseconds>(stop - start);
    cout<<"Using Extended_Bottom_Up_Cut_Rod, Maximum Obtainable Revenue is "<<ebucr_r<<endl;
    cout<<"i"<<endl;
    for(int i=0;i<=n;i++){
        cout<<"\t"<<i;
        if(i == n){
            cout<<endl;
        }
    }
    cout<<"Prices"<<endl;
    cout<<"\t0";
    for(int i=0;i<n;i++){
        cout<<"\t"<<p[i];
        if(i==n-1){
            cout<<endl;
        }
    }
    cout<<"Revenues"<<endl;
    cout_r(r,n+1);
    cout<<"Cuts"<<endl;
    cout_s(s,n+1);
    Print_Cut_Rod_Soution(s,n+1,r);
    cout << "Time taken function: "<< duration.count() << " microseconds" << endl<<endl;

    MODIFIED_CUT_ROD(p,n);
    
    return 0;
}

max revenue is 38 and with the cuts 4 ,5,1 we get35 only
i think there will be 2 cuts of 5 length each so as to get 38 as max revenue