ロッドを切るための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)))

出力

Maximum Obtainable Value is 21

すべての変数はローカルスコープで宣言されており、それらの参照は上の図に示されています。

結論

この記事では、ロッドを切断するためのPythonプログラムを作成する方法について学習しました。