Rod Cutting Problem | Dynamic Programming (with code)

In this article, we will study the rod-cutting problem, which is a classic example of a dynamic programming problem. The rod-cutting problem has several real-world applications in areas such as manufacturing, finance, and computer science.

Revisiting Dynamic Programming

Dynamic programming is an algorithmic technique that solves problems by breaking them down into smaller subproblems and storing the solutions to these subproblems in memory. This technique is often used to solve optimization problems where we want to find the maximum or minimum value of a function subject to some constraints.

The key idea behind dynamic programming is to avoid redundant computations by reusing the solutions to the subproblems. This is done by storing the solutions in a table or array, which can be accessed quickly when needed.

Dynamic programming can be classified into two main types: top-down and bottom-up.

• Top-down dynamic programming: Also known as memoization, it involves solving the problem recursively by storing the solutions to the subproblems in memory.
• Bottom-up dynamic programming: It involves solving the subproblems iteratively from the smallest subproblems to the largest subproblems.

The Rod-Cutting Problem

The Rod-Cutting Problem involves finding the maximum revenue that can be generated by cutting a rod into smaller pieces and selling those pieces at different prices.

The rod-cutting problem has an optimal substructure property, which is a key requirement for dynamic programming. This property means that the optimal solution to a problem can be obtained by combining the optimal solutions with its subproblems.

In the case of the rod cutting problem, if we know the maximum revenue that can be generated for a given length of the rod, we can break down the problem into smaller subproblems by considering all possible cut positions for that length of the rod.

For example, suppose we want to cut a rod of length n into pieces of lengths l1, l2, ..., lk to maximize the total revenue. We can start by considering all possible cut positions for a rod of length n and computing the maximum revenue that can be obtained for each position.

We can then select the cut position that gives the maximum revenue and recursively solve the subproblems of cutting the remaining pieces of the rod.

By solving each subproblem optimally and combining the solutions, we can obtain the optimal solution to the original problem. This is the key idea behind the dynamic programming approach to the rod-cutting problem, which is based on the optimal substructure property.

Problem Statement

Given a rod of length n and a list of prices for different lengths of the rod, find the maximum revenue that can be generated by cutting the rod into smaller pieces and selling those pieces at the given prices.

For example, suppose we have a rod of length 10 and the following prices:

Length: 1 2 3 4 5 6 7 8 9 10
Price: 1 5 7 8 10 13 16 19 20 21

Solution Approach

Dynamic programming can be used to solve the rod-cutting problem. We can use a bottom-up approach to build the solution in a tabular form. We can start by solving the smaller subproblems and then combine them to solve the larger problem.

Let's define a one-dimensional array, dp, where dp[i] represents the maximum revenue that can be generated by cutting a rod of length i. We can initialize dp[0] to 0 because the maximum revenue generated by a rod of length zero is zero.

For each length of the rod, we can consider all possible cuts and select the cut that generates the maximum revenue. We can use a nested loop to iterate over all possible cuts for each length of the rod.

The following recurrence relation can be used to determine dp[i]:

dp[i] = max(dp[i], price[j] + dp[i - j])

Here j is the length of the cut, and price[j] is the price of the cut of length j. The above equation means that we can either cut the rod into a piece of length j and sell it for price[j] or not cut it and continue with the remaining rod of length i - j. We select the cut that generates the maximum revenue.

After iterating over all possible cuts for each length of the rod, we can return dp[n], which represents the maximum revenue that can be generated by cutting a rod of length n.

We can cut the rod into the following pieces and generate the maximum revenue:

Length: 1 2 3 4 5 6 7 8 9 10
MaxPrice: 1 5 7 10 12 15 17 20 22 25

Maximum Revenue: 25

C++ Implementation

Let's implement the above approach in C++:

#include<bits/stdc++.h>
using namespace std;

int maxRevenue(int n, vector<int>& price) {
    vector<int> dp(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i] = max(dp[i], price[j - 1] + dp[i - j]);
        }
    }

    return dp[n];
}

int main() {
    int n = 10;
    vector<int> price = {1, 5, 7, 8, 10, 13, 16, 19, 20, 21};

    cout << "Maximum Revenue: " << maxRevenue(n, price) << endl;

    return 0;
}

Output:

Maximum Revenue: 25

Time & Space Complexity

The time complexity of the above code is O(n^2) because we are using nested loops to iterate over all possible cuts for each length of the rod. Therefore, the total number of iterations will be n*(n+1)/2, which is O(n^2).

The space complexity of the above code is O(n) because we are using a one-dimensional array dp of size n+1 to store the maximum revenue that can be generated for each length of the rod. Therefore, the space required by the program increases linearly with the length of the rod.

Iterative Approach

Similarly, let's take a look at the iterative approach using dynamic programming for the rod-cutting problem using C++:

#include<bits/stdc++.h>
using namespace std;

int maxRevenue(int n, vector<int> &price) {
    int dp[n+1];
    dp[0] = 0;

    for(int i=1; i<=n; i++) {
        int max_val = INT_MIN;
        for(int j=0; j<i; j++) {
            max_val = max(max_val, price[j] + dp[i-j-1]);
        }
        dp[i] = max_val;
    }
    return dp[n];
}


int main() {
    int n = 10;
    vector<int> price = {1, 5, 7, 8, 10, 13, 16, 19, 20, 21};

    cout << "Maximum Revenue: " << maxRevenue(n, price) << endl;

    return 0;
}

Output:

Maximum Revenue: 25

In the above algorithm, we first create an array of size n+1 to store the maximum value that can be obtained for each subproblem. We initialize the first value of the array to 0 since we cannot cut a rod of length 0.

We then use two nested loops to solve each subproblem iteratively. In the outer loop, we iterate from 1 to n, where i represents the length of the rod. In the inner loop, we iterate from 0 to i-1, where j represents the length of the left piece of the rod.

We calculate the maximum value that can be obtained by cutting the rod at position j and adding the maximum value of the two resulting subproblems. We store this maximum value in the dp array at position i.

Finally, we return the value of dp[n], which represents the maximum value that can be obtained by cutting a rod of length n.

The time complexity of the above algorithm is O(n^2), and the space complexity is O(n). The iterative approach is more efficient than the recursive approach in terms of space complexity since we do not need to store the solutions to all subproblems in memory.

Conclusion

You can now easily solve the rod-cutting problem using dynamic programming. In image processing, the rod-cutting problem can be used to crop images to a specific aspect ratio or size. In finance, this problem can be used to optimize investment portfolios by determining the best combination of stocks and bonds to maximize the returns.