Maximum product cutting using dynamic programming
Cutting a rope into smaller pieces is a common problem that arises in various scenarios. The problem statement revolves around finding the maximum product that can be obtained by cutting a given rope of a certain length into smaller pieces. In this article, we will discuss the problem, its significance, and present a dynamic programming solution to tackle it efficiently.
Problem Statement:
Given a rope of length 'n', the task is to find the maximum product that can be obtained by cutting the rope into smaller pieces. The rope can be cut into any number of pieces, and each piece has a positive integer length. The goal is to find the optimal way to cut the rope to maximize the product of the lengths of all the smaller pieces.
For example, consider a rope of length 15. The optimal way to cut the rope would be into smaller pieces of length 3, resulting in a product of 3 × 3 × 3 × 3 × 3 = 243. Similarly, for a rope of length 22, the optimal way would be to cut it into pieces of length 3, 3, 3, 3, 3, 3, and 4, resulting in a product of 2916.
Significance of the Problem:
The problem of maximum product cutting has practical applications in various domains. For instance, in manufacturing industries, materials such as ropes, wires, and fabrics often need to be cut into specific lengths for production purposes. By determining the optimal cutting strategy that maximizes the product of the lengths, companies can minimize material wastage and improve efficiency.
Dynamic Programming Solution:
To solve this problem efficiently, we can employ the principles of dynamic programming. Dynamic programming allows us to break down a complex problem into smaller subproblems and store their solutions to avoid redundant computations. Here's how we can approach this problem using dynamic programming:
Code Solution:
// 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 : 2916package 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 : 2916Define a dynamic programming array, dp[], of size 'n + 1', where dp[i] represents the maximum product that can be obtained from a rope of length 'i'.
Initialize dp[0] and dp[1] as 0 since they don't represent valid rope lengths.
For each length 'i' from 2 to 'n', iterate through all possible cuts 'j' such that 1 ≤ j ≤ i/2. Calculate the maximum product by considering two cases: a. The product of the lengths obtained by cutting the rope into two pieces: (i - j) * j. b. The product of the length 'j' and the maximum product of the remaining length: j * dp[i - j].
Update the value of dp[i] with the maximum product obtained in the previous step.
Repeat steps 3 and 4 for all lengths 'i' from 2 to 'n'.
Finally, the maximum product of cutting a rope of length 'n' can be obtained from dp[n].
Let's analyze the code provided:
The given C code implements the above dynamic programming solution for two test cases: length 15 and length 22. It defines a helper function 'max' to compare two integers and return the maximum value. The 'maxProduct' function uses the dynamic programming approach explained above to calculate the maximum product and displays the results.
The output shows that for a rope of length 15, the maximum product is 243, and for a rope of length 22, the maximum product is 2916.
Overall Time Complexity: Considering all the steps, the dominant factor in the time complexity is the nested loops, which contribute O(length) complexity. Therefore, the overall time complexity of the given program is O(length).
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