The Rod Cutting Problem is an optimization problem that aims to determine the maximum profit obtainable by cutting a rod into pieces and selling those pieces. Given a rod of a certain length and a list of prices for each piece length, the goal is to find the best way to cut the rod to maximize revenue.

Program Structure

• Input: Length of the rod and an array of prices for each length of the rod.
• Output: Maximum profit that can be obtained from cutting the rod.
• Dynamic Programming: The program uses a 1D array to store the maximum profits for different lengths of the rod.

C++ Code

#include <iostream>
#include <vector>

using namespace std;

// Function to maximize profit by cutting a rod
int rodCutting(const vector<int>& prices, int length) {
    // Create an array to store maximum profit for each length
    vector<int> dp(length + 1, 0);

    // Calculate maximum profit for each length from 1 to length
    for (int i = 1; i <= length; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i] = max(dp[i], prices[j - 1] + dp[i - j]);
        }
    }

    // Return the maximum profit for the full length of the rod
    return dp[length];
}

int main() {
    int length;

    // Input the length of the rod
    cout << "Enter the length of the rod: ";
    cin >> length;

    // Input the prices for each piece length
    vector<int> prices(length);
    cout << "Enter the prices for each piece length (1 to " << length << "): ";
    for (int i = 0; i < length; i++) {
        cin >> prices[i];
    }

    // Calculate the maximum profit
    int maxProfit = rodCutting(prices, length);

    // Output the result
    cout << "Maximum Profit: " << maxProfit << endl;

    return 0;
}

Explanation of the Code

The code consists of the following main components:

• Input Handling: The program prompts the user to enter the length of the rod and the prices for each possible piece length.
• Profit Calculation: The rodCutting function uses dynamic programming to fill a 1D array dp. Here, dp[i] represents the maximum profit obtainable from a rod of length i.
• Dynamic Programming Logic: For each length, the function iterates through all possible cuts and updates the maximum profit by comparing the current maximum profit with the profit obtained by cutting the rod at that length.
• Output: The program displays the calculated maximum profit for the given rod length.

Conclusion

This program efficiently calculates the maximum profit obtainable from cutting a rod using dynamic programming techniques, providing a clear strategy for solving optimization problems in resource allocation.