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

01.01.2020Java Программы

Дан стержень длиной 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];

}