Program Overview

This program solves the rod cutting problem, which involves determining the maximum profit obtainable by cutting a rod of a given length into pieces and selling the pieces based on their lengths and associated prices.

Program Structure

• Input: The length of the rod and an array of prices corresponding to each length.
• Dynamic Programming Table: An array to store the maximum profit obtainable for each length of the rod.
• Output: The maximum profit that can be achieved by cutting the rod into pieces.

C Program

#include 

// Function to maximize profit by cutting the rod
int rodCutting(int prices[], int n) {
    int dp[n + 1]; // Array to store maximum profit for each length
    dp[0] = 0; // No profit for a rod of length 0

    // Build the dp array
    for (int i = 1; i <= n; i++) {
        int maxProfit = -1; // Initialize max profit for the current length
        for (int j = 0; j < i; j++) { maxProfit = (maxProfit > prices[j] + dp[i - j - 1]) ? maxProfit : prices[j] + dp[i - j - 1];
        }
        dp[i] = maxProfit; // Store the maximum profit for length i
    }

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

// Main function
int main() {
    int n;

    // Input the length of the rod
    printf("Enter the length of the rod: ");
    scanf("%d", &n);

    int prices[n];

    // Input the prices for each length
    printf("Enter the prices for lengths 1 to %d:\n", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &prices[i]);
    }

    // Calculate the maximum profit
    int maxProfit = rodCutting(prices, n);
    printf("Maximum profit obtainable: %d\n", maxProfit);

    return 0;
}

Explanation of the Code

The program consists of two main parts: the function for maximizing profit and the main function to handle input and output:

• The rodCutting function implements the dynamic programming approach:
  • An array dp is created to store the maximum profit obtainable for each rod length from 0 to n.
  • The function iterates through each possible rod length and calculates the maximum profit by considering all possible first cut lengths.
  • The maximum profit for each length is stored in the dp array, and the final maximum profit for the entire rod length is returned.
• The main function handles user input:
  • The user is prompted to enter the length of the rod.
  • It then inputs the prices for each length and calls the rodCutting function to compute the maximum profit.

Usage

To use the program:

1. Compile the program using a C compiler (e.g., gcc).
2. Run the executable and input the length of the rod.
3. Input the prices for each length of the rod.
4. The program will output the maximum profit that can be achieved by cutting the rod into pieces.