Рубрики

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

Программы Python

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

# Наивное рекурсивное решение
# для проблемы резки стержня

import sys

  
# Полезная функция для получения
# максимум двух целых

def max(a, b):

    return a if (a > b) else b

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

def cutRod(price, n):

    if(n <= 0):

        return 0

    max_val = -sys.maxsize-1

      

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

    # и сравнить разные конфигурации

    for i in range(0, n):

        max_val = max(max_val, price[i] + 

                      cutRod(price, n - i - 1))

    return max_val

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

arr = [1, 5, 8, 9, 10, 17, 17, 20]

size = len(arr)

print("Maximum Obtainable Value is", cutRod(arr, size))

  
# Этот код предоставлен 'Smitha Dinesh Semwal'

Выход:

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

питон

# Динамическое программирующее решение для задачи резки стержнем

INT_MIN = -32767

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

def cutRod(price, n):

    val = [0 for x in range(n + 1)]

    val[0] = 0

  

    # Постройте таблицу val [] снизу вверх и вернитесь

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

    for i in range(1, n + 1):

        max_val = INT_MIN

        for j in range(i):

             max_val = max(max_val, price[j] + val[i-j-1])

        val[i] = max_val

  

    return val[n]

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

arr = [1, 5, 8, 9, 10, 17, 17, 20]

size = len(arr)

print("Maximum Obtainable Value is " + str(cutRod(arr, size)))

  
# Этот код предоставлен Bhavya Jain

Выход:

Maximum Obtainable Value is 22

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

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

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

0.00 (0%) 0 votes