ロッド切断問題を解くPythonプログラム：動的計画法で最大価値を求める方法

はじめに

この記事では、以下の問題文に対する解決策について学びます。

問題文

長さ n のロッドと、n より小さい各サイズの切断片の価格を格納した価格配列が与えられます。ロッドを切断し、その断片を売却したときに得られる最大の価値を求める必要があります。

この問題は、動的計画法（Dynamic Programming）を用いて解きます。

アルゴリズムの考え方

長さ i のロッドから得られる最大価値を val[i] とすると、次の漸化式が成り立ちます。

val[i] = max(price[j] + val[i-j-1])　（j = 0 ～ i-1）

これは「最初に j+1 の長さで切った場合の価格」と「残りの部分から得られる最大価値」の合計を、すべての切り方について調べることを意味します。小さい問題から順に答えを埋めていくボトムアップ方式で計算することで、全探索よりも効率的に、計算量 O(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]

# メイン処理
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

この例では、長さ8のロッドに対して価格配列 [2, 4, 7, 9, 11, 16, 16, 21] を与えており、最適な切断方法によって最大価値 21 が得られます。

すべての変数はローカルスコープ内で宣言されており、その参照関係は上図のとおりです。

まとめ

この記事では、動的計画法を用いてロッド切断問題（Rod Cutting Problem）を解くPythonプログラムの作成方法について学びました。ボトムアップ方式で部分問題の最適解を順に記録していくことで、あらゆる切断パターンを効率的に評価し、最大の売上価値を求めることができます。同様の手法は、資源の最適配分やナップサック問題など、他の多くの最適化問題にも応用できます。