Рубрики

Java-программа для резки прута | 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

// // Наивное рекурсивное решение задачи резания стержня

class RodCutting {

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

       п и цена [] как цены разных штук * /

    static int cutRod(int price[], int n)

    {

        if (n <= 0)

            return 0;

        int max_val = Integer.MIN_VALUE;

  

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

        // сравниваем разные конфигурации

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

            max_val = Math.max(max_val,

                               price[i] + cutRod(price, n - i - 1));

  

        return max_val;

    }

  

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

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

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

Выход:

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 [] снизу вверх.

Джава

// Решение динамического программирования для задачи резки стержнем

class RodCutting {

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

       длина n и цена [] как цены разных штук * /

    static int cutRod(int price[], int n)

    {

        int val[] = new int[n + 1];

        val[0] = 0;

  

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

        // последняя запись из таблицы

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

    }

  

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

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

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

Выход:

Maximum Obtainable Value is 22

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

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

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

0.00 (0%) 0 votes