Python 程式用於切割一根鋼筋

在本文中，我們將瞭解以下所述問題陳述的解決方案。

問題陳述 − 我們得到一根長度為 n 的鋼筋和一個價格陣列，其中包含所有小於 n 的尺寸的部件價格。我們需要確定透過切割鋼筋並銷售其部件獲得的最大價值。

我們將採用動態程式設計方法來解決問題。

現在讓我們觀察一下以下實現中的解決方案−

示例

# A Dynamic Programming solution for Rod cutting problem
INT_MIN = -32767
# cut function
def cutRod(price, n):
   val = [0 for x in range(n + 1)]
   val[0] = 0
   # bottom up manner
   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)))