Rod Cutting

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<<a[i]<<" ";
        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;
    cout<<"If we cut the rod of length "<<n<<" into following lengths: "<<endl;
    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]);
            int pi = r[i] > INT_MIN ? r[i] : p[i];
            cout<<"length of "<<i+1<<" whose price is $"<<p[i];
            if(r[j-i-1] > 0){
                cout<<" and the length of "<<j-i-1<<" whose price is $"<<r[j-i-1];
            }
            cout<<" we get the maximum profit of  $"<<q;
            if(p[i]+r[j-i-1] != q){
                cout<<" out of $"<<q<<" and $"<<p[i]+r[j-i-1];
            }
            cout<<endl;
        }
        r[j] = q;
    }
    return r[n];
}

int main(int argc, char const *argv[])
{
    int p[] = {1,5,8,9,10,17,17,20,24,30};
    int n = 5;
    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<<"Maximum Obtainable Revenue is "<<result<<endl;
    cout << "Time taken by naive 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<<"Maximum Obtainable Revenue is "<<result<<endl;
    cout << "Time taken by memoized cut rod 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<<"Maximum Obtainable Revenue is "<<result<<endl;
    cout << "Time taken by bottom up cut rod function: "<< duration.count() << " microseconds" << endl;
    return 0;
}

Output