用于切割杆的 Python 程序

pythonserver side programmingprogramming

在本文中，我们将了解下面给出的问题陈述的解决方案。

问题陈述− 给定一根长度为 n 的杆和一个价格数组，其中包含所有小于 n 的尺寸的杆件的价格。我们需要确定通过切割杆并出售其部件可获得的最大值。

我们将使用动态规划方法来解决这个问题。

现在让我们观察下面实现中的解决方案−

示例

# 杆切割问题的动态规划解决方案
INT_MIN = -32767
# cut 函数
def cutRod(price, n):
   val = [0 for x in range(n + 1)]
   val[0] = 0
   # 自下而上的方式
   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]
# main
arr = [2, 4, 7, 9, 11, 16, 16, 21]
size = len(arr)
print("Maximum Obtainable Value is " + str(cutRod(arr, size)))