Maximum product cutting using dynamic programming

Here given code implementation process.

// C Program
// Maximum product cutting using dynamic programming
#include <stdio.h>

int max(int a, int b)
{
	if (a > b)
	{
		return a;
	}
	return b;
}
void maxProduct(int length)
{
	if (length <= 1)
	{
		return;
	}
	int auxiliary = 0;
	int dp[length + 1];
	// Initial value
	dp[0] = 0;
	dp[1] = 0;
	for (int i = 1; i <= length; ++i)
	{
		for (int j = 1; j <= i / 2; ++j)
		{
			auxiliary = max(max(auxiliary, (i - j) * j), j * dp[i - j]);
		}
		dp[i] = auxiliary;
		auxiliary = 0;
	}
	// Display given length
	printf("\n Length  : %d", length);
	// Display calculated result
	printf("\n Product : %d", dp[length]);
}
int main()
{
	// Test A
	// length = 15
	// [3+3+3+3+3] = 15
	// 3×3×3×3×3  = 243 
	maxProduct(15);
	// Test B
	// length = 22
	// [2×2×3×3×3×3×3×3]  = 2916
	// [2+2+3+3+3+3+3+3]  = 22
	// or 
	// [3×3×3×3×3×3×4] = 2916 
	// [3+3+3+3+3+3+4] = 22  
	// etc..
	maxProduct(22);
	return 0;
}

Output

 Length  : 15
 Product : 243
 Length  : 22
 Product : 2916
// Java Program 
// Maximum product cutting using dynamic programming
public class Product
{
	public int max(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	public void maxProduct(int length)
	{
		if (length <= 1)
		{
			return;
		}
		int auxiliary = 0;
		int[] dp = new int[length + 1];
		// Initial value
		dp[0] = 0;
		dp[1] = 0;
		for (int i = 1; i <= length; ++i)
		{
			for (int j = 1; j <= i / 2; ++j)
			{
				auxiliary = max(max(auxiliary, (i - j) * j), j * dp[i - j]);
			}
			dp[i] = auxiliary;
			auxiliary = 0;
		}
		// Display given length
		System.out.print("\n Length : " + length);
		// Display calculated result
		System.out.print("\n Product : " + dp[length]);
	}
	public static void main(String[] args)
	{
		Product task = new Product();
		// Test A
		// length = 15
		// [3+3+3+3+3] = 15
		// 3×3×3×3×3  = 243 
		task.maxProduct(15);
		// Test B
		// length = 22
		// [2×2×3×3×3×3×3×3]  = 2916
		// [2+2+3+3+3+3+3+3]  = 22
		// or 
		// [3×3×3×3×3×3×4] = 2916 
		// [3+3+3+3+3+3+4] = 22  
		// etc..
		task.maxProduct(22);
	}
}

Output

 Length : 15
 Product : 243
 Length : 22
 Product : 2916
// Include header file
#include <iostream>
using namespace std;
// C++ Program 
// Maximum product cutting using dynamic programming
class Product
{
	public: int max(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	void maxProduct(int length)
	{
		if (length <= 1)
		{
			return;
		}
		int auxiliary = 0;
		int dp[length + 1];
		// Initial value
		dp[0] = 0;
		dp[1] = 0;
		for (int i = 1; i <= length; ++i)
		{
			for (int j = 1; j <= i / 2; ++j)
			{
				auxiliary = this->max(
                  this->max(auxiliary, (i - j) * j), 
                  j * dp[i - j]);
			}
			dp[i] = auxiliary;
			auxiliary = 0;
		}
		// Display given length
		cout << "\n Length : " << length;
		// Display calculated result
		cout << "\n Product : " << dp[length];
	}
};
int main()
{
	Product *task = new Product();
	// Test A
	// length = 15
	// [3+3+3+3+3] = 15
	// 3×3×3×3×3  = 243 
	task->maxProduct(15);
	// Test B
	// length = 22
	// [2×2×3×3×3×3×3×3]  = 2916
	// [2+2+3+3+3+3+3+3]  = 22
	// or 
	// [3×3×3×3×3×3×4] = 2916 
	// [3+3+3+3+3+3+4] = 22  
	// etc..
	task->maxProduct(22);
	return 0;
}

Output

 Length : 15
 Product : 243
 Length : 22
 Product : 2916
// Include namespace system
using System;
// Csharp Program 
// Maximum product cutting using dynamic programming
public class Product
{
	public int max(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	public void maxProduct(int length)
	{
		if (length <= 1)
		{
			return;
		}
		int auxiliary = 0;
		int[] dp = new int[length + 1];
		// Initial value
		dp[0] = 0;
		dp[1] = 0;
		for (int i = 1; i <= length; ++i)
		{
			for (int j = 1; j <= i / 2; ++j)
			{
				auxiliary = this.max(
                  this.max(auxiliary, (i - j) * j), 
                  j * dp[i - j]);
			}
			dp[i] = auxiliary;
			auxiliary = 0;
		}
		// Display given length
		Console.Write("\n Length : " + length);
		// Display calculated result
		Console.Write("\n Product : " + dp[length]);
	}
	public static void Main(String[] args)
	{
		Product task = new Product();
		// Test A
		// length = 15
		// [3+3+3+3+3] = 15
		// 3×3×3×3×3  = 243 
		task.maxProduct(15);
		// Test B
		// length = 22
		// [2×2×3×3×3×3×3×3]  = 2916
		// [2+2+3+3+3+3+3+3]  = 22
		// or 
		// [3×3×3×3×3×3×4] = 2916 
		// [3+3+3+3+3+3+4] = 22  
		// etc..
		task.maxProduct(22);
	}
}

Output

 Length : 15
 Product : 243
 Length : 22
 Product : 2916
package main
import "fmt"
// Go Program 
// Maximum product cutting using dynamic programming
type Product struct {}
func getProduct() * Product {
	var me *Product = &Product {}
	return me
}
func(this Product) max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func(this Product) maxProduct(length int) {
	if length <= 1 {
		return
	}
	var auxiliary int = 0
	var dp = make([] int, length + 1)
	// Initial value
	dp[0] = 0
	dp[1] = 0
	for i := 1 ; i <= length ; i++ {
		for j := 1 ; j <= i / 2 ; j++ {
			auxiliary = this.max(this.max(auxiliary, (i - j) * j), 
				j * dp[i - j])
		}
		dp[i] = auxiliary
		auxiliary = 0
	}
	// Display given length
	fmt.Print("\n Length : ", length)
	// Display calculated result
	fmt.Print("\n Product : ", dp[length])
}
func main() {
	var task * Product = getProduct()
	// Test A
	// length = 15
	// [3+3+3+3+3] = 15
	// 3×3×3×3×3  = 243 
	task.maxProduct(15)
	// Test B
	// length = 22
	// [2×2×3×3×3×3×3×3]  = 2916
	// [2+2+3+3+3+3+3+3]  = 22
	// or 
	// [3×3×3×3×3×3×4] = 2916 
	// [3+3+3+3+3+3+4] = 22  
	// etc..
	task.maxProduct(22)
}

Output

 Length : 15
 Product : 243
 Length : 22
 Product : 2916
<?php
// Php Program 
// Maximum product cutting using dynamic programming
class Product
{
	public	function max($a, $b)
	{
		if ($a > $b)
		{
			return $a;
		}
		return $b;
	}
	public	function maxProduct($length)
	{
		if ($length <= 1)
		{
			return;
		}
		$auxiliary = 0;
		$dp = array_fill(0, $length + 1, 0);
		// Initial value
		$dp[0] = 0;
		$dp[1] = 0;
		for ($i = 1; $i <= $length; ++$i)
		{
			for ($j = 1; $j <= (int)($i / 2); ++$j)
			{
				$auxiliary = $this->max(
                  $this->max($auxiliary, ($i - $j) * $j), 
                  $j * $dp[$i - $j]);
			}
			$dp[$i] = $auxiliary;
			$auxiliary = 0;
		}
		// Display given length
		echo("\n Length : ".$length);
		// Display calculated result
		echo("\n Product : ".$dp[$length]);
	}
}

function main()
{
	$task = new Product();
	// Test A
	// length = 15
	// [3+3+3+3+3] = 15
	// 3×3×3×3×3  = 243 
	$task->maxProduct(15);
	// Test B
	// length = 22
	// [2×2×3×3×3×3×3×3]  = 2916
	// [2+2+3+3+3+3+3+3]  = 22
	// or 
	// [3×3×3×3×3×3×4] = 2916 
	// [3+3+3+3+3+3+4] = 22  
	// etc..
	$task->maxProduct(22);
}
main();

Output

 Length : 15
 Product : 243
 Length : 22
 Product : 2916
// Node JS Program 
// Maximum product cutting using dynamic programming
class Product
{
	max(a, b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	maxProduct(length)
	{
		if (length <= 1)
		{
			return;
		}
		var auxiliary = 0;
		var dp = Array(length + 1).fill(0);
		// Initial value
		dp[0] = 0;
		dp[1] = 0;
		for (var i = 1; i <= length; ++i)
		{
			for (var j = 1; j <= parseInt(i / 2); ++j)
			{
				auxiliary = this.max(
                  this.max(auxiliary, (i - j) * j), j * dp[i - j]);
			}
			dp[i] = auxiliary;
			auxiliary = 0;
		}
		// Display given length
		process.stdout.write("\n Length : " + length);
		// Display calculated result
		process.stdout.write("\n Product : " + dp[length]);
	}
}

function main()
{
	var task = new Product();
	// Test A
	// length = 15
	// [3+3+3+3+3] = 15
	// 3×3×3×3×3  = 243 
	task.maxProduct(15);
	// Test B
	// length = 22
	// [2×2×3×3×3×3×3×3]  = 2916
	// [2+2+3+3+3+3+3+3]  = 22
	// or 
	// [3×3×3×3×3×3×4] = 2916 
	// [3+3+3+3+3+3+4] = 22  
	// etc..
	task.maxProduct(22);
}
main();

Output

 Length : 15
 Product : 243
 Length : 22
 Product : 2916
#  Python 3 Program 
#  Maximum product cutting using dynamic programming
class Product :
	def max(self, a, b) :
		if (a > b) :
			return a
		
		return b
	
	def maxProduct(self, length) :
		if (length <= 1) :
			return
		
		auxiliary = 0
		dp = [0] * (length + 1)
		#  Initial value
		dp[0] = 0
		dp[1] = 0
		i = 1
		while (i <= length) :
			j = 1
			while (j <= int(i / 2)) :
				auxiliary = self.max(self.max(auxiliary, 
                                              (i - j) * j), 
                                     j * dp[i - j])
				j += 1
			
			dp[i] = auxiliary
			auxiliary = 0
			i += 1
		
		#  Display given length
		print("\n Length : ", length, end = "")
		#  Display calculated result
		print("\n Product : ", dp[length], end = "")
	

def main() :
	task = Product()
	#  Test A
	#  length = 15
	#  [3+3+3+3+3] = 15
	#  3×3×3×3×3  = 243 
	task.maxProduct(15)
	#  Test B
	#  length = 22
	#  [2×2×3×3×3×3×3×3]  = 2916
	#  [2+2+3+3+3+3+3+3]  = 22
	#  or 
	#  [3×3×3×3×3×3×4] = 2916 
	#  [3+3+3+3+3+3+4] = 22  
	#  etc..
	task.maxProduct(22)

if __name__ == "__main__": main()

Output

 Length :  15
 Product :  243
 Length :  22
 Product :  2916
#  Ruby Program 
#  Maximum product cutting using dynamic programming
class Product 
	def max(a, b) 
		if (a > b) 
			return a
		end

		return b
	end

	def maxProduct(length) 
		if (length <= 1) 
			return
		end

		auxiliary = 0
		dp = Array.new(length + 1) {0}
		#  Initial value
		dp[0] = 0
		dp[1] = 0
		i = 1
		while (i <= length) 
			j = 1
			while (j <= i / 2) 
				auxiliary = self.max(self.max(auxiliary, (i - j) * j), 
                                     j * dp[i - j])
				j += 1
			end

			dp[i] = auxiliary
			auxiliary = 0
			i += 1
		end

		#  Display given length
		print("\n Length : ", length)
		#  Display calculated result
		print("\n Product : ", dp[length])
	end

end

def main() 
	task = Product.new()
	#  Test A
	#  length = 15
	#  [3+3+3+3+3] = 15
	#  3×3×3×3×3  = 243 
	task.maxProduct(15)
	#  Test B
	#  length = 22
	#  [2×2×3×3×3×3×3×3]  = 2916
	#  [2+2+3+3+3+3+3+3]  = 22
	#  or 
	#  [3×3×3×3×3×3×4] = 2916 
	#  [3+3+3+3+3+3+4] = 22  
	#  etc..
	task.maxProduct(22)
end

main()

Output

 Length : 15
 Product : 243
 Length : 22
 Product : 2916
// Scala Program 
// Maximum product cutting using dynamic programming
class Product()
{
	def max(a: Int, b: Int): Int = {
		if (a > b)
		{
			return a;
		}
		return b;
	}
	def maxProduct(length: Int): Unit = {
		if (length <= 1)
		{
			return;
		}
		var auxiliary: Int = 0;
		var dp: Array[Int] = Array.fill[Int](length + 1)(0);
		// Initial value
		dp(0) = 0;
		dp(1) = 0;
		var i: Int = 1;
		while (i <= length)
		{
			var j: Int = 1;
			while (j <= i / 2)
			{
				auxiliary = max(max(auxiliary, (i - j) * j), 
                                j * dp(i - j));
				j += 1;
			}
			dp(i) = auxiliary;
			auxiliary = 0;
			i += 1;
		}
		// Display given length
		print("\n Length : " + length);
		// Display calculated result
		print("\n Product : " + dp(length));
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Product = new Product();
		// Test A
		// length = 15
		// [3+3+3+3+3] = 15
		// 3×3×3×3×3  = 243 
		task.maxProduct(15);
		// Test B
		// length = 22
		// [2×2×3×3×3×3×3×3]  = 2916
		// [2+2+3+3+3+3+3+3]  = 22
		// or 
		// [3×3×3×3×3×3×4] = 2916 
		// [3+3+3+3+3+3+4] = 22  
		// etc..
		task.maxProduct(22);
	}
}

Output

 Length : 15
 Product : 243
 Length : 22
 Product : 2916
// Swift 4 Program 
// Maximum product cutting using dynamic programming
class Product
{
	func max(_ a: Int, _ b: Int) -> Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	func maxProduct(_ length: Int)
	{
		if (length <= 1)
		{
			return;
		}
		var auxiliary: Int = 0;
		var dp: [Int] = Array(repeating: 0, count: length + 1);
		// Initial value
		dp[0] = 0;
		dp[1] = 0;
		var i: Int = 1;
		while (i <= length)
		{
			var j: Int = 1;
			while (j <= i / 2)
			{
				auxiliary = self.max(
                  self.max(auxiliary, (i - j) * j), 
                  j * dp[i - j]);
				j += 1;
			}
			dp[i] = auxiliary;
			auxiliary = 0;
			i += 1;
		}
		// Display given length
		print("\n Length : ", length, terminator: "");
		// Display calculated result
		print("\n Product : ", dp[length], terminator: "");
	}
}
func main()
{
	let task: Product = Product();
	// Test A
	// length = 15
	// [3+3+3+3+3] = 15
	// 3×3×3×3×3  = 243 
	task.maxProduct(15);
	// Test B
	// length = 22
	// [2×2×3×3×3×3×3×3]  = 2916
	// [2+2+3+3+3+3+3+3]  = 22
	// or 
	// [3×3×3×3×3×3×4] = 2916 
	// [3+3+3+3+3+3+4] = 22  
	// etc..
	task.maxProduct(22);
}
main();

Output

 Length :  15
 Product :  243
 Length :  22
 Product :  2916
// Kotlin Program 
// Maximum product cutting using dynamic programming
class Product
{
	fun max(a: Int, b: Int): Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	fun maxProduct(length: Int): Unit
	{
		if (length <= 1)
		{
			return;
		}
		var auxiliary: Int = 0;
		val dp: Array < Int > = Array(length + 1)
		{
			0
		};
		// Initial value
		dp[0] = 0;
		dp[1] = 0;
		var i: Int = 1;
		while (i <= length)
		{
			var j: Int = 1;
			while (j <= i / 2)
			{
				auxiliary = this.max(
                  this.max(auxiliary, (i - j) * j), 
                  j * dp[i - j]);
				j += 1;
			}
			dp[i] = auxiliary;
			auxiliary = 0;
			i += 1;
		}
		// Display given length
		print("\n Length : " + length);
		// Display calculated result
		print("\n Product : " + dp[length]);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Product = Product();
	// Test A
	// length = 15
	// [3+3+3+3+3] = 15
	// 3×3×3×3×3  = 243 
	task.maxProduct(15);
	// Test B
	// length = 22
	// [2×2×3×3×3×3×3×3]  = 2916
	// [2+2+3+3+3+3+3+3]  = 22
	// or 
	// [3×3×3×3×3×3×4] = 2916 
	// [3+3+3+3+3+3+4] = 22  
	// etc..
	task.maxProduct(22);
}

Output

 Length : 15
 Product : 243
 Length : 22
 Product : 2916


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







© 2021, kalkicode.com, All rights reserved