Rod-Cutting-Problems-bottomup-dp-modifications.cpp

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>

using namespace std;

// Declaration of all functions

//Function 1
//To find the max profit earned by cutting rod when the profit of each consecutive lengths are given
/*
length   | 1   2   3   4   5   6   7   8   9   10  => consecutive lenght's cuts. Lenghts differ by 1.
--------------------------------------------------
price    | 1   5   8   9  10  17  17  20   24  30
So we can use only vector to store profit and length can be represented by using the indices.
Like profit for lenght 4 => profit[4]
*/
void maxProfitByCuttingRod(int len_of_rod, vector<int>profit);

//Function 2
//To find the max profit earned by cutting rod when the profit of varying lenghts are given
/*
length   | 1   3   4   6   7   8   9   11  => Non-consecutive lengths, They are variable.
-----------------------------------------
price    | 1   5   8   9  10   17  17  20
So we cannot use vector to store profit using indices.
we should store pair one for length and other for profit respectively.
so we will use vector<pair<int,int>>
So if v[i].first == length and v[i].second == profit for that length.
*/
void maxProfitByCuttingRod2(int len_of_rod,vector<pair<int,int>>length_profit);

//Function 3
//To find the maximum profit gained by cutting rod and minimum Cost required to cut.
/*
E.G.
length   | 1   2   3   4
------------------------
price    | 1   2   1   2
Costs    | 1   0   0   1
If length of rod = 5.
So we can see that here there are two ways to get max profit.
one way => profit = 5,cost = 5 (use 1,1,1,1,1)
another way => profit = 5,cost = 1 (use 1,2,2)
*/
void maxProfit_minCost_Cuttingrod(int len_of_rod,vector<pair<int,int>>profit_cost);

//Function 4
/*
To find the maxprofit obtained by minimum nnumber of cuts.
This is same as using cuts instead of cost in above procedure.
*/
void maxProfit_minCut_Cuttingrod(int len_of_rod,vector<int>profit);

//Function 5
// To find for every length, the number of rods of that length formed, by cutting the rod.
/*
E.G.
length   | 1   2   3   4
------------------------
price    | 1   2   1   2
Costs    | 1   0   0   1
If length of rod = 5;
then
    Maxprofit = 5 (1,1,1,2)
    MinCost = 3
    count of rods of all lengths
    length   | 1   2   3   4
    ------------------------
    price    | 3   1   0   0
*/
void CountLen_of_rod_form_bycutting_for_maxprofit(int len_of_rod,vector<int>profit);

int main(){
    while(1)
    {
        cout<<endl;
        cout<<"Enter the type of operation you wish to perform\n";
        cout<<"1> Cut the Rod when consecutive lengths are given to get maximum profit\n";
        cout<<"2> Cut the Rod when lengths and profits are given separately to get maximum profit\n";
        cout<<"3> Cut the Rod when we need minimum cuts and maximum profit\n";
        cout<<"4> Cut the Rod when we need minimum cost and maximum profit\n";
        cout<<"5> Cut the Rod to get maximum profit and print the count of each length to be obtained after cut\n";
        cout<<"6> Exit\n";

        int option;
        cin>>option;

        switch(option){
            case 1: {
                int len_of_rod;
                cout<<"Please Enter the Length of Rod to be cutted";
                cout<<endl;
                cin>>len_of_rod;
                cout<<"Please enter the Length upto which you want to enter the profit\n";
                int len;
                cin>>len;
                vector<int>profit(len+1,0);
                cout<<"Please Enter the profits one by one\n";
                for(int i=1;i<=len;++i){
                    cin>>profit[i];
                }
                maxProfitByCuttingRod(len_of_rod,profit);
                break;
            }
            case 2: {
                int len_of_rod;
                cout<<"Please Enter the Length of Rod to be cutted";
                cout<<endl;
                cin>>len_of_rod;
                cout<<"Please enter the Number of rods whose length and profit you want to enter\n";
                int n;
                cin>>n;
                cout<<"Please enter the length and then profit of each rod one by one( e.g. L0 P0 , L1 P1)\n";
                vector<pair<int,int>>length_profit(n);
                for(int i=0;i<n;++i){
                    int x,y;
                    cin>>x>>y;
                    length_profit[i]={x,y};
                }
                maxProfitByCuttingRod2(len_of_rod,length_profit);
                break;
            }
            case 3: {
                int len_of_rod;
                cout<<"Please Enter the Length of Rod to be cutted";
                cout<<endl;
                cin>>len_of_rod;
                cout<<"Please enter the Length upto which you want to enter the profit\n";
                int len;
                cin>>len;
                vector<int>profit(len+1,0);
                cout<<"Please Enter the profits one by one\n";
                for(int i=1;i<=len;++i){
                    cin>>profit[i];
                }
                maxProfit_minCut_Cuttingrod(len_of_rod,profit);
                break;
            }
            case 4: {
                int len_of_rod;
                cout<<"Please Enter the Length of Rod to be cutted";
                cout<<endl;
                cin>>len_of_rod;
                cout<<"Please enter the Number of rods or length of rod upto whose profit and cost you want to enter\n";
                int n;
                cin>>n;
                cout<<"Please enter the profit and the cost of each rod one by one( e.g. P0 C0 , P1 C1)\n";
                vector<pair<int,int>>profit_cost(n+1);
                profit_cost[0]={0,0};
                for(int i=1;i<=n;++i){
                    int x,y;
                    cin>>x>>y;
                    profit_cost[i]={x,y};
                }
                maxProfit_minCost_Cuttingrod(len_of_rod,profit_cost);
                break;
            }
            case 5: {
                int len_of_rod;
                cout<<"Please Enter the Length of Rod to be cutted";
                cout<<endl;
                cin>>len_of_rod;
                cout<<"Please enter the Length upto which you want to enter the profit\n";
                int len;
                cin>>len;
                vector<int>profit(len+1,0);
                cout<<"Please Enter the profits one by one\n";
                for(int i=1;i<=len;++i){
                    cin>>profit[i];
                }
                CountLen_of_rod_form_bycutting_for_maxprofit(len_of_rod,profit);
                break;
            }
            case 6: {
                cout<<"Thanks! Hope You have understood the working\n";
                return 0;
            }
        }
    }
    return 0;
}

// Definition of All Functions

void maxProfitByCuttingRod(int len_of_rod, vector<int>profit){
    // The number of consecutive rods upto which profit is given
    int n = profit.size();

    // Bottom up dp approach
    int table[len_of_rod+1];
    table[0]=0;
    // table filling idea from TP
    for(int i=1;i<=len_of_rod;++i){
        int profit_earned = -1000;
        for(int j=1;j<=min(i,n-1);++j){
            profit_earned = max(profit_earned,profit[j]+table[i-j]);
        }
        table[i]=profit_earned;
    }
    cout<<"Hence the max profit earned by cutting rod of Given Length "<<len_of_rod;
    cout<<endl;
    cout<<"With conditions that we are provided with profits of consecutive lengths upto "<<n-1;
    cout<<endl;
    cout<<"is\n";
    cout<<table[len_of_rod];
    cout<<endl;
}

void maxProfitByCuttingRod2(int len_of_rod,vector<pair<int,int>>length_profit){
    // The number of pairs
    int n = length_profit.size();
    // In the pair first part corresponds to lenght and second one corresponds to cost
    // Bottom up approach
    int table[1+len_of_rod];
    table[0]=0;
    //table filling
    for(int i=1;i<=len_of_rod;++i){
        int profit_earned = -1000;
        for(int j=0;j<=min(i,n-1);++j){
            if(i-length_profit[j].first>=0) // checking if its possible to remove rod of length_profit[j].first length from rod of i length
                profit_earned = max(profit_earned,length_profit[j].second+table[i-length_profit[j].first]);
        }
        table[i]=profit_earned;
    }
    cout<<"Hence the max profit earned by cutting rod of Given Length "<<len_of_rod;
    cout<<endl;
    cout<<"With conditions that we are provided with lengths and profits of rods upto "<<n;
    cout<<endl;
    cout<<"is\n";
    cout<<table[len_of_rod]<<endl;
}

void maxProfit_minCut_Cuttingrod(int len_of_rod, vector<int>profit){
    int n = profit.size();
    // Bottom up approach
    // pair first part corresponds to profit and second one to number of cuts
    pair<int,int> table[1+len_of_rod];
    table[0].first=0;
    table[0].second=0;
    //table filling
    for(int i=1;i<=len_of_rod;++i){
        int profit_earned = -1000;
        int cuts = 1000;
        for(int j=1;j<=min(i,n-1);++j){
                int val = profit[j]+table[i-j].first;
                if(val>profit_earned)
                {
                    profit_earned = val;
                    cuts = table[i-j].second+1;
                }
                else if(val == profit_earned){
                    cuts = min(cuts,table[i-j].second+1);
                }
        }
        table[i].first=profit_earned;
        table[i].second = cuts;
    }
    cout<<"Hence the max profit earned by cutting rod of Given Length "<<len_of_rod;
    cout<<endl;
    cout<<"With conditions that we are provided with profits of rods of consecutive lengths upto "<<n-1;
    cout<<endl;
    cout<<"and we have to do it in min cuts possible is\n";
    cout<<table[len_of_rod].first<<endl;
    cout<<"The Number of cuts made "<<table[len_of_rod].second<<endl;
}

void maxProfit_minCost_Cuttingrod(int len_of_rod,vector<pair<int,int>>profit_cost){
    int n = profit_cost.size();
    // Bottom up approach
    // pair first part corresponds to profit and second one to number of cuts
    pair<int,int> table[1+len_of_rod];
    table[0].first=0;
    table[0].second=0;
    //table filling
    for(int i=1;i<=len_of_rod;++i){
        int profit_earned = -1000;
        int costs = 1000;
        for(int j=1;j<=min(i,n-1);++j){
                int val = profit_cost[j].first+table[i-j].first;
                if(val>profit_earned)
                {
                    profit_earned = val;
                    costs = table[i-j].second+profit_cost[j].second;
                }
                else if(val == profit_earned){
                    costs = min(costs,table[i-j].second+profit_cost[j].second);
                }
        }
        table[i].first = profit_earned;
        table[i].second = costs;
    }
    cout<<"Hence the max profit earned by cutting rod of Given Length "<<len_of_rod;
    cout<<endl;
    cout<<"With conditions that we are provided with profits of rods of consecutive lengths upto "<<n-1;
    cout<<endl;
    cout<<"and we have to do it in min costs possible is\n";
    cout<<table[len_of_rod].first<<endl;
    cout<<"The min cost made "<<table[len_of_rod].second<<endl;
}

void CountLen_of_rod_form_bycutting_for_maxprofit(int len_of_rod,vector<int>profit){
    int n = profit.size();

    // Bottom up dp approach
    pair<int,vector<int>> table[len_of_rod+1];
    table[0].first=0;
    table[0].second={};
    map<int,int>m;
    // To store key => length of rod and value => its count
    // table filling idea from TP
    for(int i=1;i<=len_of_rod;++i){
        int profit_earned = -1000;
        vector<int> len_of_cuts;
        for(int j=1;j<=min(i,n-1);++j){
            int val = profit[j]+table[i-j].first;
            if(val>profit_earned)
            {
                profit_earned = val;
                len_of_cuts = table[i-j].second;
                len_of_cuts.push_back(j);
            }
        }
        table[i].first=profit_earned;
        table[i].second = len_of_cuts;
    }
    cout<<"Hence the max profit earned by cutting rod of Given Length "<<len_of_rod;
    cout<<endl;
    cout<<"With conditions that we are provided with profits of consecutive lengths upto "<<n-1;
    cout<<endl;
    cout<<"is\n";
    cout<<table[len_of_rod].first;
    cout<<endl;
    cout<<"The Different type of length of cuts with their counts are given below\n";
    for(auto a:table[len_of_rod].second)
    m[a]++;
    for(auto a:m){
        cout<<a.first<<" "<<a.second<<endl;
    }
}