Рубрики

PHP-программа для резки прута | DP-13

Дан стержень длиной n дюймов и массив цен, содержащий цены на все кусочки размером меньше n. Определите максимальное значение, которое можно получить, разрезая прут и продавая кусочки. Например, если длина стержня равна 8, а значения разных кусков заданы следующим образом, то максимально достижимое значение равно 22 (путем разрезания на два отрезка длиной 2 и 6).


length   | 1   2   3   4   5   6   7   8  
--------------------------------------------
price    | 1   5   8   9  10  17  17  20

И если цены следующие, то максимальная доступная стоимость равна 24 (путем разрезания на восемь частей длины 1)

length   | 1   2   3   4   5   6   7   8  
--------------------------------------------
price    | 3   5   8   9  10  17  17  20

<?php
// Наивное рекурсивное решение для
// Проблема резки прута

  
/ * Возвращает лучшее доступное

   цена на стержень длиной n и

   цена [] как цены разные

   частей */

function cutRod( $price, $n)

{

  

    if ($n <= 0)

        return 0;

    $max_val = PHP_INT_MIN;

      

    // рекурсивно обрезаем стержень по разному

    // штук и сравнивать разные

    // конфигурации

    for ($i = 0; $i < $n; $i++)

            $max_val = max($max_val, $price[$i] + 

                    cutRod($price, $n - $i - 1));

      

    return $max_val;

}

  

    // Код драйвера

    $arr = array(1, 5, 8, 9, 10, 17, 17, 20);

    $size =count($arr);

    echo "Maximum Obtainable Value is ", cutRod($arr, $size);

  
// Этот код предоставлен anuj_67.
?>

Выход:

Maximum Obtainable Value is 22

Учитывая вышеописанную реализацию, ниже приведено дерево рекурсии для стержня длиной 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)

В приведенном выше дереве частичной рекурсии cR (2) решается дважды. Мы видим, что есть много подзадач, которые решаются снова и снова. Поскольку те же самые подзадачи вызываются снова, эта проблема имеет свойство Перекрывающиеся подзадачи. Таким образом, задача обрезки стержней имеет оба свойства (см. Это и это ) задачи динамического программирования. Как и другие типичные проблемы динамического программирования (DP) , повторных вычислений с одинаковыми подзадачами можно избежать, построив временный массив val [] снизу вверх.

PHP

<?php
// Решение для динамического программирования
// Проблема резки прута

  
/ * Возвращает лучшую доступную цену
для стержня длины n и цены [] как
цены на разные штуки * /

function cutRod( $price, $n)

{

    $val = array();

    $val[0] = 0;

    $i; $j;

      

    // Строим таблицу val [] внизу

    // вверх и вернуть последний

    // запись из таблицы

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

}

  
// Программа драйвера для проверки вышеуказанных функций

$arr = array(1, 5, 8, 9, 10, 17, 17, 20);

$size = count($arr);

echo "Maximum Obtainable Value is "

                      cutRod($arr, $size);

      
// Этот код предоставлен anuj_67.
?>

Выход:

Maximum Obtainable Value is 22

Пожалуйста, ознакомьтесь с полной статьей на Cutting a Rod | DP-13 для более подробной информации!

Рекомендуемые посты:

PHP-программа для резки прута | DP-13

0.00 (0%) 0 votes