Skip to main content

Rod Cutting Problem

The rod cutting problem is a classic optimization problem in computer science where the goal is to maximize the profit obtained by cutting a rod of length n into smaller pieces and selling them. Each piece has a different value depending on its length, and the objective is to find the best way to cut the rod to maximize the total profit.

Dynamic programming is a commonly used technique to solve this problem. The key idea behind dynamic programming is to break the problem down into smaller subproblems and store the results of these subproblems to avoid redundant computations.

The following is the dynamic programming algorithm to solve the rod cutting problem:

  1. Create a table to store the maximum profit for each possible rod length from 0 to n.
  2. Initialize the table with 0 for rod length 0.
  3. For each rod length i from 1 to n, compute the maximum profit by considering all possible cuts: a. For each possible cut length j from 1 to i, compute the maximum profit obtained by cutting the rod into two pieces of length j and i-j. The maximum profit is the sum of the profits obtained by selling the two pieces separately. b. Update the maximum profit for rod length i in the table with the maximum profit obtained in step 3a.
  4. The maximum profit for rod length n is the value stored in the table for length n.

Here's the Python code implementation of the dynamic programming algorithm for the rod cutting problem:

def rod_cutting(prices, n):
    table = [0] * (n+1)
    for i in range(1, n+1):
        max_profit = 0
        for j in range(i):
            max_profit = max(max_profit, prices[j] + table[i-j-1])
        table[i] = max_profit
    return table[n]


prices = [1, 2, 5, 13, 17, 19, 19, 24]
n = len(prices)
print(rod_cutting(prices, n)) # Output: 26

In the code above, n and prices are arrays containing the possible n and their respective prices. The n parameter is the length of the rod to be cut, and the function returns the maximum profit that can be obtained by cutting the rod.

Here given code implementation process.

// 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;
}

Output

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));
	}
}

Output

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;
}

Output

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));
	}
}

Output

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();

Output

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();

Output

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()

Output

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()

Output

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));
	}
}

Output

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();

Output

Max profit are  26
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment