Rod Cutting Problem - Dynamic Programming

Problem Statement

Given a rod of length “ n ” inches and an array of prices consisting of the prices of all pieces of size less than n. Your job is to figure out how much maximum money you can make, by cutting up the rod.

Example 1:

Input :
n: = 8
Prices[]:  = [1, 5, 8, 9, 10, 17, 17, 20]
Output: 22

Explanation: From the above example, we can see that the most profit is obtained when the rod is cut at 2,6 positions, this can be explained below. Given that n=8 and price array, we can expand the length as below. length[] = [1, 2,  3,  4,   5,   6,    7,    8] Price []: = [1,  5,  8,  9,  10, 17, 17, 20]

So from the above, we shou ld keep below following points in our mind:

1. We can cut the rod at any random position, but the thing is the summation of all positions cut should contribute to the original rod length.
2. Simultaneously, we should add the corresponding prices[i] to check the maximum value

From the above example, the maximum profit can be obtained from length 2,6 i,e (2+6=8) and 5+17=22 which is the maximum profit.

Example 2:

Input :
n: = 8
Prices[]:  = [3  , 5 ,  8 ,  9 , 10 , 17 , 17,  20]
Output: 24

Explanation: From the above example, we can see that the most profit is obtained when the rod is cut at 1cm length of 8 pieces.

Approach :

This problem is very similar to the Unbounded Knapsack Problem, in which the same object appears multiple times.

• Time Complexity: O(N^2)
• Space Complexity :O(N^2)

Approach 1 : (Recursion)

1. One solution to this problem is to create all possible combinations of different pieces and then find the one with the highest price.
2. In terms of time complexity, this solution is exponential.

Optimal Substructure: If an optimal solution to a given problem can be obtained by using optimal solutions to its subproblems, the problem has the Optimal Substructure Property.

Overlapping Subproblems:

1. Like Divide and Conquer, Dynamic Programming blends solutions to sub-problems. When solutions to the same subproblems are needed repeatedly, Dynamic Programming is used.
2. In dynamic programming, computed solutions of the recursive calls are placed in a table, so that they do not have to be recomputed again.
3. Dynamic Programming cannot be used if there are no common (overlapping) subproblems since storing the solutions is useless if they are never used again.

Algorithm: The idea behind this is very simple:

1. we have to partition the rod into two arbitrary  segments and just start applying the recursive function on two parts
2. In each step, we should check the profit and terminate it whenever it is maximized.
3. The above idea can be simplified into a small formula:

rod cutting(N) = max { prices[i – 1] + rodCuting(N – i) }

where 1 <= i <= N

Recursion Calls:

Python Approach (recursion)

#For the Rod cutting problem, a naive recursive solution is given.
import sys

# A utility function for calculating the sum of two integers.
def maxi(a, b):
    return a if (a > b) else b
    
# Returns the best price for a rod of length n # and price[] as prices of various segments
def Rodcutting(prices, n1):
    if(n1 <= 0):
        return 0
    max_val = -sys.maxsize-1
    
# Cut the rod in various parts in a recursive manner # and compare different configurations
    for i in range(0, n1):
        max_val = maxi(max_val, prices[i] +Rodcutting(prices, n1 - i - 1))
    return max_val

# Driver program
prices =  [1,  5,  8,  9,  10, 17, 17, 20]
length = len(prices)
print("The maximum value that can be obtained is", Rodcutting(prices , length))
print()

Java Approach (Recursion)

// A Naive Approach for finding out the highest profit by cutting the road
public class Main
{
/* Returns the best available price for a rod of length n and price[] as individual piece prices */
	static int rodcutting(int prices[], int n1)
	{
		if (n1 <= 0)
			return 0;
		int max_val = Integer.MIN_VALUE;

	// Cut the rod in various parts recursively and compare different configurations
		for (int i = 0; i<n1; i++)
			max_val = Math.max(max_val,prices[i] + rodcutting(prices, n1-i-1));

		return max_val;
	}
/* A driver programme to evaluate the functions mentioned above */
	public static void main(String args[])
	{
		int prices[] = new int[]  {1,  5,  8,  9,  10, 17, 17, 20};
		int length = prices.length;
		System.out.println("The highest value that can be gotten is:"+rodcutting(prices, length));
		System.out.println();

	}
}

C++ Approach (Recursion)

// A recursive naive solution to the Rod cutting problem
#include <stdio.h>
#include <limits.h>

// A function that returns the sum of two integers.
int max(int a, int b) 
{
    return (a > b)? a : b;
    
}

/* Returns the best available price for a rod of length n and price[] as individual piece prices */
int Rodcutting(int prices[], int n1)
{
if (n1 <= 0)
    return 0;
int max_val = INT_MIN;

// Cut the rod in various sections and compare different configurations in a recursive manner.
for (int i = 0; i<n1; i++)
        max_val = max(max_val, prices[i] +Rodcutting(prices, n1-i-1));

return max_val;
}

/* A driver programme to evaluate the functions mentioned above */
int main()
{
    int prices[] = {1, 5, 8, 9, 10, 17, 17, 20};
    int length = sizeof(prices)/sizeof(prices[0]);
    
    printf("The maximum value that can be obtained is %d", Rodcutting(prices, length));

    getchar();

    return 0;
    
}

Approach 2 (Dynamic Programming)

Efficient Approach :

1. From the above Recursion calls Figure, we can see that there are several subproblems that are solved repeatedly. This problem has the Overlapping Subproblems property since the same problems occur twice.
2. As a result, the Rod Cutting problem has both properties of a complex programming problem (Optimal substructure and overlapping subproblem).
3. Recomputations of the same subproblems, like other common Dynamic Programming (DP) problems, can be avoided by constructing a temporary array.

Algorithm: The Complete Algorithm is identical to the recursive one, with the exception that we will declare an extra key functionality to store pre-computed values.

• Time Complexity:  O(n^2)
• Space Complexity:  O(n^2)

Python version (Dynamic programming)

# A Complex Programming solution for the problem of rod cutting
INT_MIN = -32767

# Returns the best price for a rod of length n and # price[] as prices of various segments.
def Rodcutting(prices, n1):
    val = [0 for x in range(n1+1)]
    val[0] = 0
# Build the table val[] from the bottom up and return # the table's last entry.
    for i in range(1, n1+1):
        max_val = INT_MIN
        for j in range(i):
            max_val = max(max_val, prices[j] + val[i-j-1])
        val[i] = max_val

    return val[n1]
# A driver programme is used to evaluate the functions mentioned above.
prices = [1, 5, 8, 9, 10, 17, 17, 20]
length = len(prices)
print("The Maximum Achievable Value is: " + str(Rodcutting(prices, length)))
print()

Java  version (Dynamic programming)

// A Dynamic Programming Approach for the problem of rod cutting
public class Main
{
	/* Returns the best obtainable price for a rod of
	length n and price[] as prices of different pieces */
	static int Rodcutting(int prices[],int n1)
	{
		int val[] = new int[n1+1];
		val[0] = 0;

	// Build the table val[] from the bottom up and return / the table's last entry.
		for (int i = 1; i<=n1; i++)
		{
			int max_val = Integer.MIN_VALUE;
			for (int j = 0; j < i; j++)
				max_val = Math.max(max_val,
								prices[j] + val[i-j-1]);
			val[i] = max_val;
		}

		return val[n1];
	}
/* A driver programme to evaluate the functions mentioned above */
	public static void main(String args[])
	{
		int prices[] = new int[] {1, 5, 8, 9, 10, 17, 17, 20};
		int length = prices.length;
		System.out.println("The highest value that can be obtained " +
							Rodcutting(prices, length));
		System.out.println();
	}
}

C version (Dynamic programming)

// A Dynamic Programming solution for Rod cutting problem
#include <stdio.h>
#include <limits.h>
// A utility function to get the maximum of two integers
int max(int a, int b)
{ return (a > b)? a : b;
    
}

/* Returns the best obtainable price for a rod of length n and
price[] as prices of different pieces */
int Rodcutting(int prices[], int n1)
{
int val[n1+1];
val[0] = 0;
int i, j;

// Build the table val[] in bottom up manner and return the last entry
// from the table
for (i = 1; i<=n1; i++)
{
    int max_val = INT_MIN;
    for (j = 0; j < i; j++)
        max_val = max(max_val, prices[j] + val[i-j-1]);
    val[i] = max_val;
}

return val[n1];
}

/* Driver program to test above functions */
int main()
{
    int prices[] = {1, 5, 8, 9, 10, 17, 17, 20};
    int length = sizeof(prices)/sizeof(prices[0]);
    printf("The maximum value that can be obtained is %d", Rodcutting(prices, length));
    getchar();
    printf("\n");
    return 0;
}

Conclusion

We discovered the following fundamentals in the preceding article:

1. What is the concept of the rod cutting problem?
2. What is the optimal substructure?
3. What is the property of overlapping subproblems?

We also learned the step-by-step method for solving the Rod Cutting, as well as its course. We used the Naive Approach and the Dynamic Programming Approach to accomplish this. We hope that you will be able to solve this problem and its variants without difficulty now.

Happy Coding!

People are also reading:

• Breadth First Search- Graph: DSA
• DSA – Dynamic Programming
• Union vs Structure
• Python List or Array
• How to Write Pseudocode
• How to find and remove loops in a Linked List?
• Circular Doubly Linked List
• Pattern Program in C
• Rearrange an array such that arr[i] = i
• Convert a Binary Tree to Doubly Linked List
• Merge Two Sorted Arrays in-place
• Find whether an array is subset of another array