ロッドカッティング（Rod Cutting）とは？動的計画法で棒の最大売上を求める方法

長さ n の一本の棒（ロッド）が与えられ、それと同時に「長さごとの価格表」も提供されます。この問題では、棒をいくつかに切断して市場で売却したときに得られる最大の利益を求めます。

最適な価格を得るためには、さまざまな位置で切断を試み、それぞれの場合の売上を比較する必要があります。

ここで、長さ n の棒を切断したときの最大価格を返す関数を f(n) とします。この f(n) は次のように定義できます。

f(n) := price[i] + f(n − i − 1) の最大値（i は 0 から n − 1 の範囲）

これは典型的な動的計画法（DP）の問題であり、短い棒から順に最適解を求めていき、それを利用しながら長い棒の最適解を構築することで効率的に計算できます。

入力と出力

入力：

各長さの価格リストと、棒の長さ。ここでは棒の長さを 8 とします。

出力：

販売後の最大利益は 22 です。

棒を長さ 2 と 6 に切断すると、利益は 5 + 17 = 22 となり、これが最適な切断方法です。

アルゴリズム

rodCutting(price, n)

入力： 価格リスト、およびリスト内の価格の個数。

出力： 棒を切断して得られる最大利益。

処理の流れは以下の擬似コードの通りです。サイズ n+1 の利益配列を用意し、長さ 1 から n まで順番に、それぞれの長さにおける最大利益を計算していきます。

Begin
    define profit array of size n + 1
    profit[0] := 0
    for i := 1 to n, do
        maxProfit := -∞
        for j := 0 to i-1, do
            maxProfit := maximum of maxProfit and (price[j] + profit[i-j-1])
        done

        profit[i] := maxProfit
    done
    return maxProfit
End

このアルゴリズムの計算量は二重ループにより O(n²) となり、追加で使用するメモリは O(n) です。

実装例（C++）

#include <iostream>
using namespace std;

int max(int a, int b) {
    return (a > b)? a : b;
}

int rodCutting(int price[], int n) {     //価格リストと長さnから最大利益を求める
    int profit[n+1];
    profit[0] = 0;
    int maxProfit;

    for (int i = 1; i<=n; i++) {
        maxProfit = INT_MIN;     //初期値は負の無限大に設定
        for (int j = 0; j < i; j++)
            maxProfit = max(maxProfit, price[j] + profit[i-j-1]);
        profit[i] = maxProfit;
    }
    return maxProfit;
}

int main() {
    int priceList[] = {1, 5, 8, 9, 10, 17, 17, 20};
    int rodLength = 8;
    cout << "Maximum Price: "<< rodCutting(priceList, rodLength);
}

出力結果

Maximum Price: 22

このように、動的計画法を用いることで、全ての切断パターンを網羅的に評価しながら、効率よく最大利益を求めることができます。