C++でロッドカッティング問題を解く：棒の切断による最大利益を求めるプログラム

長さ n の棒（ロッド）と、各長さに対応する価格リストが与えられているとします。このとき、棒を適切な位置で切断して市場で売却することで得られる最大の利益を求めるのが、いわゆる「ロッドカッティング問題」です。さまざまな位置で切断した場合の売上を比較し、最も高い利益を実現できる切り方を見つける必要があります。

例えば、入力が prices = [1, 5, 8, 9, 10, 17, 17, 20]、n = 8 の場合、出力は 22 になります。これは、棒を長さ 2 と 6 に切断すると、利益が 5 + 17 = 22 となるためです。

解法のアプローチ

この問題は動的計画法（DP）を使うことで効率的に解くことができます。手順は以下の通りです。

• サイズ n+1 の配列 profit を定義します。
• profit[0] := 0 と初期化します。
• i = 1 から n まで繰り返し処理を行います。
  • maxProfit := 負の無限大 とします。
  • j = 0 から i-1 まで繰り返し処理を行います。
    • maxProfit := max(maxProfit, price[j] + profit[i − j − 1])
  • profit[i] := maxProfit とします。
• 最後に maxProfit を返します。

ここで、price[j] + profit[i − j − 1] は「長さ j+1 の部分をそのまま売った場合の価格」と「残りの部分に対するこれまでの最適解」を組み合わせた値を意味します。すべての切断位置を試すことで、全体の最適解が得られます。

C++での実装例

それでは、実際のコードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
int max(int a, int b) {
    return (a > b)? a : b;
}
int rodCutting(int price[], int 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 << rodCutting(priceList, rodLength);
}

入力

{1, 5, 8, 9, 10, 17, 17, 20}, 8

出力

22

計算量について

このアルゴリズムの時間計算量は O(n²)、空間計算量は O(n) です。すべての切断パターンを総当たりする素朴な再帰的手法では O(2ⁿ) の計算量が必要となりますが、動的計画法を用いることで大幅に高速化でき、実用的な規模の入力にも対応できます。