Skip to main content

Rod Cutting

 #include <iostream>

#include <vector>

using namespace std;


int rodCutting(int n, vector<int> &price) {

    vector<int> dp(n + 1, 0);

    for (int len = 1; len <= n; len++) {

        for (int cut = 1; cut <= len; cut++) {

            dp[len] = max(dp[len], price[cut - 1] + dp[len - cut]);

        }

    }

    return dp[n];

}


int main() {

    int n;

    cin >> n;

    vector<int> price(n);

    for (int i = 0; i < n; i++) cin >> price[i];

    cout << rodCutting(n, price) << endl;

    return 0;

}


// 1. Standard Rod Cutting (Maximum Profit)
int rodCuttingMaxProfit(vector<int>& price, int n) {
    vector<int> dp(n+1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            dp[i] = max(dp[i], price[j] + dp[i - j - 1]);
        }
    }
    return dp[n];
}

// 2. Minimum Number of Pieces for Maximum Profit
pair<int, int> rodCuttingMinPieces(vector<int>& price, int n) {
    vector<int> dp(n+1, 0), cuts(n+1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[i] < price[j] + dp[i-j-1]) {
                dp[i] = price[j] + dp[i-j-1];
                cuts[i] = 1 + cuts[i-j-1];
            }
        }
    }
    return {dp[n], cuts[n]};
}

// 3. Rod Cutting with Cutting Cost
int rodCuttingWithCost(vector<int>& price, int n, int cutCost) {
    vector<int> dp(n+1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            int cut = (i == j+1) ? 0 : cutCost;  // no cost if no actual cut
            dp[i] = max(dp[i], price[j] + dp[i-j-1] - cut);
        }
    }
    return dp[n];
}

// 4. Rod Cutting with Limited Supply of Each Length
int rodCuttingLimitedSupply(vector<int>& price, vector<int>& limit, int n) {
    vector<int> dp(n+1, 0);
    for (int i = 0; i < price.size(); i++) {
        for (int k = 0; k < limit[i]; k++) {
            for (int j = n; j >= i+1; j--) {
                dp[j] = max(dp[j], price[i] + dp[j - i - 1]);
            }
        }
    }
    return dp[n];
}

// 5. Rod Cutting with Exact Number of Pieces
int rodCuttingExactK(vector<int>& price, int n, int K) {
    vector<vector<int>> dp(n+1, vector<int>(K+1, INT_MIN));
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            for (int k = 1; k <= K; k++) {
                if (dp[i-j-1][k-1] != INT_MIN)
                    dp[i][k] = max(dp[i][k], dp[i-j-1][k-1] + price[j]);
            }
        }
    }
    return dp[n][K];
}

// 6. Rod Cutting with Forbidden Cuts
int rodCuttingForbidden(vector<int>& price, int n, unordered_set<int>& forbidden) {
    vector<int> dp(n+1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (forbidden.count(j+1)) continue;
            dp[i] = max(dp[i], price[j] + dp[i - j - 1]);
        }
    }
    return dp[n];
}

// 7. Rod Cutting with Only Allowed Lengths
int rodCuttingAllowed(vector<int>& price, int n, unordered_set<int>& allowed) {
    vector<int> dp(n+1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (allowed.count(j+1))
                dp[i] = max(dp[i], price[j] + dp[i-j-1]);
        }
    }
    return dp[n];
}

// 8. Rod Cutting with Minimum Waste
int rodCuttingMinWaste(vector<int>& requiredLengths, int rodLength) {
    vector<int> dp(rodLength+1, INT_MAX);
    dp[0] = 0;
    for (int len : requiredLengths) {
        for (int i = rodLength; i >= len; i--) {
            if (dp[i-len] != INT_MAX)
                dp[i] = min(dp[i], dp[i-len]);
        }
    }
    for (int i = rodLength; i >= 0; i--) {
        if (dp[i] != INT_MAX)
            return rodLength - i;
    }
    return rodLength;
}

Comments

Post a Comment

Popular Posts

An Ode to Rain

  An Ode to Rain “So what’s your favourite time of the year?” she asked, swinging a crossed foot lazily in the air, as she swirled a stirrer in a tiny cup of hot chocolate. Perhaps the time when I used to lick melted drops of vanilla from the back of my hand? blind to the fact that I was painting a modern art piece on the pavement with ice cream. What a charming memory.  Summer, I should say.  What about the little shivers my feet do, tucked away in the layers of heavy blankets, while my nose and ears complain of the biting cold to my toes.   Hot soups, lazy mornings, clouds from the mouth when I speak and hoodies with cosy pockets to slide my hands into.  Winter beats summer, surely.  To be fair, I was born in spring, the perfect gradient from the cold seasons to hot summers. Just the right temperature, reasonably humid with a drizzle of rain here and there. It had never been dramatic enough to create a lasting memory of itself though. Glancing out the caf...
1 comment
Read more

My Notes-app Up For Auction

It’s a late night with Alex Turner on full blast in my ears, never on the speakers though.  To make others around feel the full weight of unsolicited emotion of music, feels wrong. Who am I kidding, perhaps they don’t feel a thing. How rude. The flair of words seems to have abandoned me today so it’ll be bare bones. I find myself constantly backspacing the words I type with a vigour. A quickly written sentence followed by a slight pause full of fear, before my finger reaches out to the delete button on the far right. Desperately trying to put the tarp back on naked emotions uncovered bare. No more backspacing though. I’ve even gotten rid of the Grammarly extension. It shows me how a sentence rephrased, sounds more assertive but I digress. Enough fine tuning. Times like these I wish I had a typewriter. Imagine a canvas pedestal with hands, pointing to the parts where the acrylic paints fail to smudge. No one would ever pick up a paintbrush. Okay, enough rambling. This would have bee...
1 comment
Read more

1940 - Siege of Calais

(Audio enhances reading experience) 21 May 1940 “My good men, I come to you with grave news. The beaches of Calais will continue to be lonely tomorrow. There will be no boats at dawn.  Word has come from London and it seems lads, ‘home’, has just been turned to a mere word of nostalgia and not something we can hope to see, ever again.  The fat politicians sitting in parliament have sent their gravest apologies and perhaps think that we have surrendered to the Germans already. The Prime Minister has personally put in his apology through the wire too, cursing our enemy to his full capacity.  I did not bother noting down all that. Because I don’t for one moment believe in surrender, or defeat. Yes, even defeat. We men of war may lose our lives in the coming hours but with God himself as our witness I can assure you good lads.. A soldier never dies in vain nor defeat!  ‘Home’, has just been turned to a mere word of nostalgia and not something we can hope to s...
2 comments
Read more