Rod Cutting

Algorithms

The Rod Cutting problem finds the maximum revenue obtainable by cutting a rod of length $n$ into pieces, where each piece of length $i$ has a price $p_{i}$ .

Problem Statement

Given a rod of length $n$ and prices for pieces of different lengths, determine the maximum revenue by cutting the rod optimally.

Dynamic Programming Solution

We use dynamic programming where $d p [i]$ represents the maximum revenue for a rod of length $i$ .

Time Complexity

The time complexity is $O (n^{2})$ , where $n$ is the length of the rod.

Implementation

def rod_cutting(prices):
    """Dynamic Programming approach to solve the Rod Cutting problem."""
    n = len(prices)
    
    # Initialize dp array where dp[i] is the maximum revenue for rod of length i
    dp = [0] * (n + 1)
    
    # Compute maximum revenue for each length from 1 to n
    for i in range(1, n + 1):
        max_val = -float('inf')
        for j in range(1, i + 1):
            max_val = max(max_val, prices[j - 1] + dp[i - j])
        dp[i] = max_val
    
    return dp[n]

# Example usage:
prices = [2, 5, 9, 10, 15, 17, 17, 20]
print("Maximum revenue: {}".format(rod_cutting(prices)))  # Output: 22