Рубрики

C Программа для резки стержня | 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

// Наивное рекурсивное решение задачи резания стержня
#include <limits.h>
#include <stdio.h>

  
// Вспомогательная функция для получения максимум двух целых

int max(int a, int b) { return (a > b) ? a : b; }

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

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

int cutRod(int price[], int n)

{

    if (n <= 0)

        return 0;

    int max_val = INT_MIN;

  

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

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

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

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

  

    return max_val;

}

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

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;

}

Выход:

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

C ++

// Решение динамического программирования для задачи резки стержнем
#include <limits.h>
#include <stdio.h>

  
// Вспомогательная функция для получения максимум двух целых

int max(int a, int b) { return (a > b) ? a : b; }

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

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

int cutRod(int price[], int n)

{

    int val[n + 1];

    val[0] = 0;

    int i, j;

  

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

    // из таблицы

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

}

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

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;

}

Выход:

Maximum Obtainable Value is 22

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

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

C Программа для резки стержня | DP-13

0.00 (0%) 0 votes