Rod Cutting Problem

The Rod Cutting Problem is a classic optimization problem that falls under the category of dynamic programming. The problem involves finding the maximum revenue that can be obtained by cutting a rod of length 'n' into smaller pieces and selling them based on their individual prices. Each rod length has a specific price, and the goal is to determine the best way to cut the rod to maximize the total revenue. In this article, we will explore the problem statement, understand the underlying concepts, and implement an efficient solution using dynamic programming.

Problem Statement

Given a rod of length 'n' and an array 'price' that contains the prices of different rod lengths, we need to find the maximum revenue that can be obtained by cutting the rod into smaller pieces and selling them.

Example

Let's consider a rod of length 'n = 8' and the array of prices for rod lengths:

length:     1   2   3   4   5   6   7   8
price:      1   2   5   13  17  19  19  24

The goal is to find the maximum revenue that can be obtained from cutting the rod.

Dynamic Programming Approach

Dynamic programming is a powerful technique used to solve problems with overlapping subproblems. It efficiently stores the solutions to subproblems to avoid redundant calculations. To solve the Rod Cutting Problem, we can use dynamic programming in two common ways: memoization (top-down) or tabulation (bottom-up). Let's implement the tabulation approach:

1. Initialize an array dp of size 'n+1' to store the maximum revenue that can be obtained for each rod length from 0 to 'n'.
2. Set the initial value of dp[0] to 0 since there is no revenue for a rod of length 0.
3. For each rod length 'i' from 1 to 'n': a. Initialize a variable max_val to store the maximum revenue for the current rod length 'i'. b. For each cut length 'j' from 1 to 'i':
   • Calculate the revenue if we cut the rod of length 'i' at position 'j' and sell both pieces.
   • Update max_val with the maximum of its current value and the calculated revenue. c. Store the maximum revenue max_val in dp[i].
4. The maximum revenue for the rod of length 'n' will be stored in dp[n].

Algorithm Explanation

function max_value(a, b):
    if a > b:
        return a
    else:
        return b

function cut_rod(price[], n):
    dp[n + 1]
    dp[0] = 0
    for i from 1 to n:
        max_val = -infinity
        for j from 1 to i:
            max_val = max_value(max_val, price[j] + dp[i - j])
        dp[i] = max_val
    return dp[n]

Code Solution

Here given code implementation process.

• C
• Java
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

// C program
// Rod Cutting Problem 
#include <stdio.h>

#include <limits.h>

// Return a maximum value in given two numbers
int max_value(int a, int b)
{
	if (a > b)
	{
		return a;
	}
	else
	{
		return b;
	}
}
int cut_rod(int price[], int n)
{
	//Auxiliary space to calculate result
	int result[n + 1];
	int max_val = INT_MIN;
	//Loop controlling variables
	int i = 0;
	int j = 0;
	//Set the first result value
	result[i] = 0;
	//Outer loop
	for (i = 1; i <= n; i++)
	{
		//Inner loop
		for (j = 0; j < i; j++)
		{
			max_val = max_value(max_val, price[j] + result[i - j - 1]);
		}
		// Put the calculated max value
		result[i] = max_val;
		// Reset the max value
		max_val = INT_MIN;
	}
	return result[n];
}
int main()
{
	int price[] = {
		1,
		2,
		5,
		13,
		17,
		19,
		19,
		24
	};
	// Actual rod size from (1 to n)
	// Get total number of price
	int size = sizeof(price) / sizeof(price[0]);
	printf("Max profit are %d", cut_rod(price, size));
	return 0;
}

Max profit are 26

// Java Program 
// Rod Cutting Problem 
class RodCutting
{
	// Return a maximum value in given two numbers
	public int max_value(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	public int cut_rod(int[] price, int n)
	{
		//Auxiliary space to calculate result
		int[] result = new int[n + 1];
		int max_val = Integer.MIN_VALUE;
		//Loop controlling variables
		int i = 0;
		int j = 0;
		//Set the first result value
		result[i] = 0;
		//Outer loop
		for (i = 1; i <= n; i++)
		{
			//Inner loop
			for (j = 0; j < i; j++)
			{
				max_val = max_value(max_val, price[j] + result[i - j - 1]);
			}
			// Put the calculated max value
			result[i] = max_val;
			// Reset the max value
			max_val = Integer.MIN_VALUE;
		}
		return result[n];
	}
	public static void main(String[] args)
	{
		//Make object 
		RodCutting obj = new RodCutting();
		int[] price = {
			1,
			2,
			5,
			13,
			17,
			19,
			19,
			24
		};
		// Get total number of price
		int size = price.length;
		System.out.print("Max profit are " + obj.cut_rod(price, size));
	}
}

Max profit are 26

//Include header file
#include <iostream>
#include<limits.h>
using namespace std;

// C++ Program 
// Rod Cutting Problem 

class RodCutting
{
	public:
		// Return a maximum value in given two numbers
		int max_value(int a, int b)
		{
			if (a > b)
			{
				return a;
			}
			else
			{
				return b;
			}
		}
	int cut_rod(int price[], int n)
	{
		//Auxiliary space to calculate result
		int result[n+1];
		int max_val = INT_MIN;
		//Loop controlling variables
		int i = 0;
		int j = 0;
		//Set the first result value
		result[i] = 0;
		//Outer loop
		for (i = 1; i <= n; i++)
		{
			//Inner loop
			for (j = 0; j < i; j++)
			{
				max_val = this->max_value(max_val, price[j] + result[i - j - 1]);
			}
			// Put the calculated max value
			result[i] = max_val;
			// Reset the max value
			max_val = INT_MIN;
		}
		return result[n];
	}
};
int main()
{
	//Make object 
	RodCutting obj = RodCutting();
	int price[] = {
		1 , 2 , 5 , 13 , 17 , 19 , 19 , 24
	};
	// Get total number of price
	int size = sizeof(price) / sizeof(price[0]);
	cout << "Max profit are " << obj.cut_rod(price, size);
	return 0;
}

Max profit are 26

//Include namespace system
using System;

// C# Program 
// Rod Cutting Problem 

class RodCutting
{
	// Return a maximum value in given two numbers
	public int max_value(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	public int cut_rod(int[] price, int n)
	{
		//Auxiliary space to calculate result
		int[] result = new int[n + 1];
		int max_val = int.MinValue;
		//Loop controlling variables
		int i = 0;
		int j = 0;
		//Set the first result value
		result[i] = 0;
		//Outer loop
		for (i = 1; i <= n; i++)
		{
			//Inner loop
			for (j = 0; j < i; j++)
			{
				max_val = max_value(max_val, price[j] + result[i - j - 1]);
			}
			// Put the calculated max value
			result[i] = max_val;
			// Reset the max value
			max_val = int.MinValue;
		}
		return result[n];
	}
	public static void Main(String[] args)
	{
		//Make object 
		RodCutting obj = new RodCutting();
		int[] price = {
			1 , 2 , 5 , 13 , 17 , 19 , 19 , 24
		};
		// Get total number of price
		int size = price.Length;
		Console.Write("Max profit are " + obj.cut_rod(price, size));
	}
}

Max profit are 26

<?php

// Php Program 
// Rod Cutting Problem 

class RodCutting
{
	// Return a maximum value in given two numbers
	public	function max_value($a, $b)
	{
		if ($a > $b)
		{
			return $a;
		}
		else
		{
			return $b;
		}
	}
	public	function cut_rod( $price, $n)
	{
		//Auxiliary space to calculate result
		$result = array_fill(0, $n + 1, 0);
		$max_val = -PHP_INT_MAX;
		//Loop controlling variables
		$i = 0;
		$j = 0;
		//Set the first result value
		$result[$i] = 0;
		//Outer loop
		for ($i = 1; $i <= $n; $i++)
		{
			//Inner loop
			for ($j = 0; $j < $i; $j++)
			{
				$max_val = $this->max_value($max_val, $price[$j] + $result[$i - $j - 1]);
			}
			// Put the calculated max value
			$result[$i] = $max_val;
			// Reset the max value
			$max_val = -PHP_INT_MAX;
		}
		return $result[$n];
	}
}

function main()
{
	//Make object 
	$obj = new RodCutting();
	$price = array(1, 2, 5, 13, 17, 19, 19, 24);
	// Get total number of price
	$size = count($price);
	echo "Max profit are ". $obj->cut_rod($price, $size);
}
main();

Max profit are 26

// Node Js Program 
// Rod Cutting Problem 
class RodCutting
{
	// Return a maximum value in given two numbers
	max_value(a, b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	cut_rod(price, n)
	{
		//Auxiliary space to calculate result
		var result = Array(n + 1).fill(0);
		var max_val = -Number.MAX_VALUE;
		//Loop controlling variables
		var i = 0;
		var j = 0;
		//Outer loop
		for (i = 1; i <= n; i++)
		{
			//Inner loop
			for (j = 0; j < i; j++)
			{
				max_val = this.max_value(max_val, price[j] + result[i - j - 1]);
			}
			// Put the calculated max value
			result[i] = max_val;
			// Reset the max value
			max_val = -Number.MAX_VALUE;
		}
		return result[n];
	}
}

function main()
{
	//Make object 
	var obj = new RodCutting();
	var price = [1, 2, 5, 13, 17, 19, 19, 24];
	// Get total number of price
	var size = price.length;
	process.stdout.write("Max profit are " + obj.cut_rod(price, size));
}
main();

Max profit are 26

import sys

#  Python 3 Program 
#  Rod Cutting Problem 

class RodCutting :
	#  Return a maximum value in given two numbers
	def max_value(self, a, b) :
		if (a > b) :
			return a
		else :
			return b
		
	
	def cut_rod(self, price, n) :
		# Auxiliary space to calculate result
		result = [0] * (n + 1)
		max_val = -sys.maxsize
		# Loop controlling variables
		i = 1
		j = 0
		while (i <= n) :
			# Inner loop
			j = 0
			while (j < i) :
				max_val = self.max_value(max_val, price[j] + result[i - j - 1])
				j += 1
			
			#  Put the calculated max value
			result[i] = max_val
			#  Reset the max value
			max_val = -sys.maxsize
			i += 1
		
		return result[n]
	

def main() :
	# Make object 
	obj = RodCutting()
	price = [1, 2, 5, 13, 17, 19, 19, 24]
	#  Get total number of price
	size = len(price)
	print("Max profit are ", obj.cut_rod(price, size), end = "")

if __name__ == "__main__": main()

Max profit are  26

#  Ruby Program 
#  Rod Cutting Problem 

class RodCutting 
	#  Return a maximum value in given two numbers
	def max_value(a, b) 
		if (a > b) 
			return a
		else 
			return b
		end
	end
	def cut_rod(price, n) 
		# Auxiliary space to calculate result
		result = Array.new(n + 1) {0}
		max_val = -(2 ** (0. size * 8 - 2))
		# Loop controlling variables
		i = 1
		j = 0
		while (i <= n) 
			# Inner loop
			j = 0
			while (j < i) 
				max_val = self.max_value(max_val, price[j] + result[i - j - 1])
				j += 1
			end
			#  Put the calculated max value
			result[i] = max_val
			#  Reset the max value
			max_val = -(2 ** (0. size * 8 - 2))
			i += 1
		end
		return result[n]
	end
end
def main() 
	# Make object 
	obj = RodCutting.new()
	price = [1, 2, 5, 13, 17, 19, 19, 24]
	#  Get total number of price
	size = price.length
	print("Max profit are ", obj.cut_rod(price, size))
end
main()

Max profit are 26

// Scala Program 
// Rod Cutting Problem 

class RodCutting
{
	// Return a maximum value in given two numbers
	def max_value(a: Int, b: Int): Int = {
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	def cut_rod(price: Array[Int], n: Int): Int = {
		//Auxiliary space to calculate result
		var result: Array[Int] = Array.fill[Int](n + 1)(0);
		var max_val: Int = Int.MinValue;
		//Loop controlling variables
		var i: Int = 1;
		var j: Int = 0;
		while (i <= n)
		{
			//Inner loop
			j = 0;
			while (j < i)
			{
				max_val = max_value(max_val, price(j) + result(i - j - 1));
				j += 1;
			}
			// Put the calculated max value
			result(i) = max_val;
			// Reset the max value
			max_val = Int.MinValue;
			i += 1;
		}
		return result(n);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		//Make object 
		var obj: RodCutting = new RodCutting();
		var price: Array[Int] = Array(1, 2, 5, 13, 17, 19, 19, 24);
		// Get total number of price
		var size: Int = price.length;
		print("Max profit are " + obj.cut_rod(price, size));
	}
}

Max profit are 26

// Swift 4 Program 
// Rod Cutting Problem 

class RodCutting
{
	// Return a maximum value in given two numbers
	func max_value(_ a: Int, _ b: Int) -> Int
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	func cut_rod(_ price: [Int], _ n: Int) -> Int
	{
		//Auxiliary space to calculate result
		var result: [Int] = Array(repeating: 0, count: n + 1);
		var max_val: Int = Int.min;
		//Loop controlling variables
		var i: Int = 1;
		var j: Int = 0;
		while (i <= n)
		{
			//Inner loop
			j = 0;
			while (j < i)
			{
				max_val = self.max_value(max_val, price[j] + result[i - j - 1]);
				j += 1;
			}
			// Put the calculated max value
			result[i] = max_val;
			// Reset the max value
			max_val = Int.min;
			i += 1;
		}
		return result[n];
	}
}
func main()
{
	//Make object 
	let obj: RodCutting = RodCutting();
	let price: [Int] = [1, 2, 5, 13, 17, 19, 19, 24];
	// Get total number of price
	let size: Int = price.count;
	print("Max profit are ", obj.cut_rod(price, size), terminator: "");
}
main();

Max profit are  26

Output Explanation

For the given example with rod length 'n = 8' and the array of prices, the output will be:

Max profit is 26

This means that by cutting the rod of length 8 into two pieces of lengths 2 and 6, we can achieve the maximum revenue of 26, which is obtained by adding the prices of these two pieces (2 + 24).

Time Complexity Analysis

The time complexity of the dynamic programming approach is O(n^2). This is because of the two nested loops in the cut_rod function. However, this problem can be solved more efficiently using dynamic programming with a time complexity of O(n) by using memoization or tabulation methods.

Finally

The Rod Cutting Problem is a classic optimization problem that can be efficiently solved using dynamic programming. By employing the tabulation approach, we can find the maximum revenue that can be obtained by cutting a given rod into smaller pieces with different lengths and prices. The dynamic programming technique optimizes the solution by avoiding redundant calculations, making it an effective method for solving complex problems with overlapping subproblems.