Dada uma barra de comprimento n polegadas e uma array de preços que contém 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 a seguir, 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

A seguir está a implementação recursiva simples do problema do corte da haste. A implementação simplesmente segue a estrutura recursiva mencionada acima.

<?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.
?>

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) está sendo 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 maneira ascendente.

<?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.
?>

O valor máximo obtido é 22

Consulte o artigo completo sobre Corte de uma haste | DP-13 para mais detalhes!