Program Explanation

The Rod Cutting Problem involves maximizing the profit from cutting a rod of a given length into smaller
pieces, where each piece has a specific profit associated with its length. This program uses dynamic programming
to efficiently compute the maximum profit by considering all possible ways to cut the rod.

Program Structure

1. Function Definition: The main function is maxProfit(length int, prices []int) int,
   which takes the total length of the rod and an array of prices (profit for each length) as input and
   returns the maximum profit obtainable.
2. Dynamic Programming Table: A 1D slice dp is created to store the maximum
   profit for each length of the rod.
3. Logic: A loop iterates through each length of the rod:
   • For each length, the program checks all possible cuts and updates the maximum profit achievable
     by comparing the current profit with the profit obtained by cutting the rod into two pieces.
4. Result: The maximum profit for the full length of the rod is found in the last element
   of the DP table.

Go Code

package main

import (
    "fmt"
)

// maxProfit calculates the maximum profit obtainable by cutting a rod.
func maxProfit(length int, prices []int) int {
    // Create a DP array to store maximum profit for each length
    dp := make([]int, length+1)
    
    // Calculate maximum profit for each length
    for i := 1; i <= length; i++ {
        maxVal := 0
        for j := 1; j <= i; j++ {
            if j <= len(prices) { maxVal = max(maxVal, prices[j-1]+dp[i-j]) } } dp[i] = maxVal } // The maximum profit for the full length of the rod return dp[length] } // max returns the maximum of two integers. func max(a, b int) int { if a > b {
        return a
    }
    return b
}

func main() {
    // Example rod length and prices for different lengths
    length := 8
    prices := []int{0, 1, 5, 8, 9, 10, 17, 17, 20}
    
    profit := maxProfit(length, prices)
    fmt.Printf("Maximum Profit: %d\n", profit)
}

Explanation of the Code:

• Function maxProfit(length int, prices []int) int:
  • This function computes the maximum profit obtainable by cutting a rod of a specified length using dynamic programming.
  • It initializes a 1D slice dp, where dp[i] represents the maximum profit that can be obtained for a rod of length i.
• Dynamic Programming Array (dp):
  • The length of the dp array is length + 1, where length is the total length of the rod.
  • The program calculates the maximum profit for each length by checking all possible cuts.
• Logic for Filling the DP Array:
  • For each length i, the program iterates through all possible cuts j (from 1 to i).
  • If a cut of length j is possible (i.e., j is within the bounds of the prices array), it calculates the potential profit by summing the price of the cut and the maximum profit of the remaining rod length (i-j).
  • It updates dp[i] with the maximum profit found.
• Function max(a, b int) int:
  • A utility function that returns the maximum of two integers.

How to Run the Program:

1. Save the code as main.go.
2. Open your terminal and navigate to the directory containing the file.
3. Run the command go run main.go.

This program effectively demonstrates the solution to the rod cutting problem using dynamic programming, providing a clear method for maximizing profits.

Conclusion

This Go program efficiently solves the Rod Cutting Problem using dynamic programming. The algorithm
has a time complexity of O(n^2), where n is the length of the rod. This method provides a practical
solution for maximizing profits in various scenarios, such as production and resource allocation.