Cortando uma haste | DP-13
Dada uma barra de comprimento de n polegadas e uma array de preços que inclui preços de todas as peças de tamanho menores que n. Determine o valor máximo que pode ser obtido cortando a haste e vendendo as peças. Por exemplo, se o comprimento da haste é 8 e os valores das diferentes peças são dados como a seguir, então o valor máximo que pode ser obtido é 22 (cortando duas peças de comprimentos 2 e 6)
length | 1 2 3 4 5 6 7 8 -------------------------------------------- price | 1 5 8 9 10 17 17 20
E se os preços forem os seguintes, então o valor máximo que pode ser obtido é 24 (cortando em oito pedaços de comprimento 1)
length | 1 2 3 4 5 6 7 8 -------------------------------------------- price | 3 5 8 9 10 17 17 20
Uma solução ingênua para esse problema é gerar todas as configurações de peças diferentes e encontrar a configuração de preço mais alto. Essa solução é exponencial em termos de complexidade de tempo. Vejamos como esse problema possui propriedades importantes de um problema de programação dinâmica (DP) e pode ser resolvido de forma eficiente usando a programação dinâmica.
1) Subestrutura Ótima:
Podemos obter o melhor preço fazendo um corte em diferentes posições e comparando os valores obtidos após um corte. Podemos chamar recursivamente a mesma função para uma peça obtida após um corte.
Seja cutRod (n) o valor necessário (melhor preço possível) para uma barra de comprimento n. cutRod (n) pode ser escrito da seguinte maneira.
cutRod (n) = max (preço [i] + cutRod (ni-1)) para todo i em {0, 1 .. n-1}
2) Subproblemas sobrepostos
A seguir está uma implementação recursiva simples do problema do corte da haste.
A implementação simplesmente segue a estrutura recursiva mencionada acima.
// A Naive recursive 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 cutRod(int price[], int n)
{
if (n <= 0)
return 0;
int max_val = INT_MIN;
// Recursively cut the rod in different pieces and compare different
// configurations
for (int i = 0; i<n; i++)
max_val = max(max_val, price[i] + cutRod(price, n-i-1));
return max_val;
}
/* Driver program to test above functions */
int main()
{
int arr[] = {1, 5, 8, 9, 10, 17, 17, 20};
int size = sizeof(arr)/sizeof(arr[0]);
printf("Maximum Obtainable Value is %d", cutRod(arr, size));
getchar();
return 0;
}// // A Naive recursive solution for Rod cutting problem
class RodCutting
{
/* Returns the best obtainable price for a rod of length
n and price[] as prices of different pieces */
static int cutRod(int price[], int n)
{
if (n <= 0)
return 0;
int max_val = Integer.MIN_VALUE;
// Recursively cut the rod in different pieces and
// compare different configurations
for (int i = 0; i<n; i++)
max_val = Math.max(max_val,
price[i] + cutRod(price, n-i-1));
return max_val;
}
/* Driver program to test above functions */
public static void main(String args[])
{
int arr[] = new int[] {1, 5, 8, 9, 10, 17, 17, 20};
int size = arr.length;
System.out.println("Maximum Obtainable Value is "+
cutRod(arr, size));
}
}
/* This code is contributed by Rajat Mishra */# A Naive recursive solution
# for Rod cutting problem
import sys
# A utility function to get the
# maximum of two integers
def max(a, b):
return a if (a > b) else b
# Returns the best obtainable price for a rod of length n
# and price[] as prices of different pieces
def cutRod(price, n):
if(n <= 0):
return 0
max_val = -sys.maxsize-1
# Recursively cut the rod in different pieces
# and compare different configurations
for i in range(0, n):
max_val = max(max_val, price[i] +
cutRod(price, n - i - 1))
return max_val
# Driver code
arr = [1, 5, 8, 9, 10, 17, 17, 20]
size = len(arr)
print("Maximum Obtainable Value is", cutRod(arr, size))
# This code is contributed by 'Smitha Dinesh Semwal'// A Naive recursive solution for
// Rod cutting problem
using System;
class GFG {
/* Returns the best obtainable
price for a rod of length
n and price[] as prices of
different pieces */
static int cutRod(int []price, int n)
{
if (n <= 0)
return 0;
int max_val = int.MinValue;
// Recursively cut the rod in
// different pieces and compare
// different configurations
for (int i = 0; i < n; i++)
max_val = Math.Max(max_val, price[i] +
cutRod(price, n - i - 1));
return max_val;
}
// Driver Code
public static void Main()
{
int []arr = new int[] {1, 5, 8, 9, 10, 17, 17, 20};
int size = arr.Length;
Console.WriteLine("Maximum Obtainable Value is "+
cutRod(arr, size));
}
}
// This code is contributed by Sam007<?php
// A Naive recursive solution for
// Rod cutting problem
/* Returns the best obtainable
price for a rod of length n and
price[] as prices of different
pieces */
function cutRod( $price, $n)
{
if ($n <= 0)
return 0;
$max_val = PHP_INT_MIN;
// Recursively cut the rod in different
// pieces and compare different
// configurations
for ($i = 0; $i < $n; $i++)
$max_val = max($max_val, $price[$i] +
cutRod($price, $n - $i - 1));
return $max_val;
}
// Driver Code
$arr = array(1, 5, 8, 9, 10, 17, 17, 20);
$size =count($arr);
echo "Maximum Obtainable Value is "
, cutRod($arr, $size);
// This code is contributed anuj_67.
?><script>
// A Naive recursive solution for
// Rod cutting problem
/* Returns the best obtainable
price for a rod of length
n and price[] as prices of
different pieces */
function cutRod(price, n)
{
if (n <= 0)
return 0;
let max_val = Number.MIN_VALUE;
// Recursively cut the rod in
// different pieces and compare
// different configurations
for (let i = 0; i < n; i++)
max_val = Math.max(max_val, price[i] +
cutRod(price, n - i - 1));
return max_val;
}
let arr = [1, 5, 8, 9, 10, 17, 17, 20];
let size = arr.length;
document.write("Maximum Obtainable Value is "+ cutRod(arr, size));
</script>Saída
O valor máximo obtido é 22
Considerando a implementação acima, a seguir está a árvore de recursão para uma haste de comprimento 4.
cR() ---> cutRod()
cR(4)
/ /
/ /
cR(3) cR(2) cR(1) cR(0)
/ | / |
/ | / |
cR(2) cR(1) cR(0) cR(1) cR(0) cR(0)
/ | |
/ | |
cR(1) cR(0) cR(0) cR(0)
/
/
CR(0)
Na árvore de recursão parcial acima, cR (2) é resolvido duas vezes. Podemos ver que existem muitos subproblemas que são resolvidos continuamente. Como os mesmos subproblemas são chamados novamente, esse problema possui a propriedade Overlapping Subproblems. Portanto, o problema do corte da haste tem as duas propriedades (veja isto e aquilo ) de um problema de programação dinâmica. Como outros problemas típicos de Programação Dinâmica (DP) , recomputações dos mesmos subproblemas podem ser evitadas construindo um array temporário val [] de uma maneira ascendente.
// 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 cutRod(int price[], int n)
{
int val[n+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<=n; i++)
{
int max_val = INT_MIN;
for (j = 0; j < i; j++)
max_val = max(max_val, price[j] + val[i-j-1]);
val[i] = max_val;
}
return val[n];
}
/* Driver program to test above functions */
int main()
{
int arr[] = {1, 5, 8, 9, 10, 17, 17, 20};
int size = sizeof(arr)/sizeof(arr[0]);
printf("Maximum Obtainable Value is %d", cutRod(arr, size));
getchar();
return 0;
}// A Dynamic Programming solution for Rod cutting problem
class RodCutting
{
/* Returns the best obtainable price for a rod of
length n and price[] as prices of different pieces */
static int cutRod(int price[],int n)
{
int val[] = new int[n+1];
val[0] = 0;
// Build the table val[] in bottom up manner and return
// the last entry from the table
for (int i = 1; i<=n; i++)
{
int max_val = Integer.MIN_VALUE;
for (int j = 0; j < i; j++)
max_val = Math.max(max_val,
price[j] + val[i-j-1]);
val[i] = max_val;
}
return val[n];
}
/* Driver program to test above functions */
public static void main(String args[])
{
int arr[] = new int[] {1, 5, 8, 9, 10, 17, 17, 20};
int size = arr.length;
System.out.println("Maximum Obtainable Value is " +
cutRod(arr, size));
}
}
/* This code is contributed by Rajat Mishra */# A Dynamic Programming solution for Rod cutting problem
INT_MIN = -32767
# Returns the best obtainable price for a rod of length n and
# price[] as prices of different pieces
def cutRod(price, n):
val = [0 for x in range(n+1)]
val[0] = 0
# Build the table val[] in bottom up manner and return
# the last entry from the table
for i in range(1, n+1):
max_val = INT_MIN
for j in range(i):
max_val = max(max_val, price[j] + val[i-j-1])
val[i] = max_val
return val[n]
# Driver program to test above functions
arr = [1, 5, 8, 9, 10, 17, 17, 20]
size = len(arr)
print("Maximum Obtainable Value is " + str(cutRod(arr, size)))
# This code is contributed by Bhavya Jain// A Dynamic Programming solution
// for Rod cutting problem
using System;
class GFG {
/* Returns the best obtainable
price for a rod of length n
and price[] as prices of
different pieces */
static int cutRod(int []price,int n)
{
int []val = new int[n + 1];
val[0] = 0;
// Build the table val[] in
// bottom up manner and return
// the last entry from the table
for (int i = 1; i<=n; i++)
{
int max_val = int.MinValue;
for (int j = 0; j < i; j++)
max_val = Math.Max(max_val,
price[j] + val[i - j - 1]);
val[i] = max_val;
}
return val[n];
}
// Driver Code
public static void Main()
{
int []arr = new int[] {1, 5, 8, 9, 10, 17, 17, 20};
int size = arr.Length;
Console.WriteLine("Maximum Obtainable Value is " +
cutRod(arr, size));
}
}
// This code is contributed by Sam007<?php
// A Dynamic Programming solution for
// Rod cutting problem
/* Returns the best obtainable price
for a rod of length n and price[] as
prices of different pieces */
function cutRod( $price, $n)
{
$val = array();
$val[0] = 0;
$i; $j;
// Build the table val[] in bottom
// up manner and return the last
// entry from the table
for ($i = 1; $i <= $n; $i++)
{
$max_val = PHP_INT_MIN;
for ($j = 0; $j < $i; $j++)
$max_val = max($max_val,
$price[$j] + $val[$i-$j-1]);
$val[$i] = $max_val;
}
return $val[$n];
}
// Driver program to test above functions
$arr = array(1, 5, 8, 9, 10, 17, 17, 20);
$size = count($arr);
echo "Maximum Obtainable Value is ",
cutRod($arr, $size);
// This code is contributed by anuj_67.
?><script>
// A Dynamic Programming solution
// for Rod cutting problem
/* Returns the best obtainable
price for a rod of length n
and price[] as prices of
different pieces */
function cutRod(price, n)
{
let val = new Array(n + 1);
val[0] = 0;
// Build the table val[] in
// bottom up manner and return
// the last entry from the table
for (let i = 1; i<=n; i++)
{
let max_val = Number.MIN_VALUE;
for (let j = 0; j < i; j++)
max_val = Math.max(max_val, price[j] + val[i - j - 1]);
val[i] = max_val;
}
return val[n];
}
let arr = [1, 5, 8, 9, 10, 17, 17, 20];
let size = arr.length;
document.write("Maximum Obtainable Value is " + cutRod(arr, size) + "n");
</script>Saída
O valor máximo obtido é 22
A complexidade de tempo da implementação acima é O (n ^ 2), que é muito melhor do que a complexidade de tempo de pior caso da implementação Naive recursiva.
3) Usando a ideia de mochila ilimitada.
Esse problema é muito semelhante ao Problema da mochila sem limites, em que há várias ocorrências do mesmo item. Aqui estão os pedaços da vara.
Agora vou criar uma analogia entre a mochila sem limites e o problema do corte da haste.
// CPP program for above approach
#include <iostream>
using namespace std;
// Global Array for
// the purpose of memoization.
int t[9][9];
// A recursive program, using ,
// memoization, to implement the
// rod cutting problem(Top-Down).
int un_kp(int price[], int length[],
int Max_len, int n)
{
// The maximum price will be zero,
// when either the length of the rod
// is zero or price is zero.
if (n == 0 || Max_len == 0)
{
return 0;
}
// If the length of the rod is less
// than the maximum length, Max_lene will
// consider it.Now depending
// upon the profit,
// either Max_lene we will take
// it or discard it.
if (length[n - 1] <= Max_len)
{
t[n][Max_len]
= max(price[n - 1]
+ un_kp(price, length,
Max_len - length[n - 1], n),
un_kp(price, length, Max_len, n - 1));
}
// If the length of the rod is
// greater than the permitted size,
// Max_len we will not consider it.
else
{
t[n][Max_len]
= un_kp(price, length,
Max_len, n - 1);
}
// Max_lene Max_lenill return the maximum
// value obtained, Max_lenhich is present
// at the nth roMax_len and Max_lenth column.
return t[n][Max_len];
}
/* Driver program to
test above functions */
int main()
{
int price[] = { 1, 5, 8, 9, 10, 17, 17, 20 };
int n = sizeof(price) / sizeof(price[0]);
int length[n];
for (int i = 0; i < n; i++) {
length[i] = i + 1;
}
int Max_len = n;
// Function Call
cout << "Maximum obtained value is "
<< un_kp(price, length, n, Max_len) << endl;
}// C program for above approach
#include <stdio.h>
#include <stdlib.h>
int max(int a, int b)
{
return (a > b) ? a : b;
}
// Global Array for the
// purpose of memoization.
int t[9][9];
// A recursive program, using ,
// memoization, to implement the
// rod cutting problem(Top-Down).
int un_kp(int price[], int length[],
int Max_len, int n)
{
// The maximum price will be zero,
// when either the length of the rod
// is zero or price is zero.
if (n == 0 || Max_len == 0)
{
return 0;
}
// If the length of the rod is less
// than the maximum length, Max_lene
// will consider it.Now depending
// upon the profit,
// either Max_lene we will take it
// or discard it.
if (length[n - 1] <= Max_len)
{
t[n][Max_len]
= max(price[n - 1]
+ un_kp(price, length,
Max_len - length[n - 1], n),
un_kp(price, length, Max_len, n - 1));
}
// If the length of the rod is greater
// than the permitted size, Max_len
// we will not consider it.
else
{
t[n][Max_len]
= un_kp(price, length,
Max_len, n - 1);
}
// Max_lene Max_lenill return
// the maximum value obtained,
// Max_lenhich is present at the
// nth roMax_len and Max_lenth column.
return t[n][Max_len];
}
/* Driver program to test above functions */
int main()
{
int price[] = { 1, 5, 8, 9, 10, 17, 17, 20 };
int n = sizeof(price) / sizeof(price[0]);
int length[n];
for (int i = 0; i < n; i++)
{
length[i] = i + 1;
}
int Max_len = n;
// Function Call
printf("Maximum obtained value is %d \n",
un_kp(price, length, n, Max_len));
}<script>
// Javascript program for above approach
// Global Array for
// the purpose of memoization.
let t = new Array(9);
for (var i = 0; i < t.length; i++) {
t[i] = new Array(2);
}
// A recursive program, using ,
// memoization, to implement the
// rod cutting problem(Top-Down).
function un_kp(price, length, Max_len, n)
{
// The maximum price will be zero,
// when either the length of the rod
// is zero or price is zero.
if (n == 0 || Max_len == 0)
{
return 0;
}
// If the length of the rod is less
// than the maximum length, Max_lene will
// consider it.Now depending
// upon the profit,
// either Max_lene we will take
// it or discard it.
if (length[n - 1] <= Max_len)
{
t[n][Max_len]
= Math.max(price[n - 1]
+ un_kp(price, length,
Max_len - length[n - 1], n),
un_kp(price, length, Max_len, n - 1));
}
// If the length of the rod is
// greater than the permitted size,
// Max_len we will not consider it.
else
{
t[n][Max_len]
= un_kp(price, length,
Max_len, n - 1);
}
// Max_lene Max_lenill return the maximum
// value obtained, Max_lenhich is present
// at the nth roMax_len and Max_lenth column.
return t[n][Max_len];
}
// Driver code
let price = [ 1, 5, 8, 9, 10, 17, 17, 20 ];
let n = price.length;
let length = Array(n).fill(0);
for (let i = 0; i < n; i++) {
length[i] = i + 1;
}
let Max_len = n;
// Function Call
document.write("Maximum obtained value is "
+ un_kp(price, length, n, Max_len));
</script>Saída
O valor máximo obtido é 22
<iframe allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen="" frameborder="0" height="374" src="https://www.youtube.com/embed/oqdttaJ_C6o?feature=oembed" width="665"></iframe>
Escreva comentários se encontrar algo incorreto ou se quiser compartilhar mais informações sobre o tópico discutido acima.
As postagens do blog Acervo Lima te ajudaram? Nos ajude a manter o blog no ar!
Faça uma doação para manter o blog funcionando.
70% das doações são no valor de R$ 5,00...
Diógenes Lima da Silva
