ロッドカッティング

さまざまな位置でカットし、ロッドをカットした後の価格を比較することで、最良の価格を得るには。

長さnの行を切り取った後、f（n）が可能な最大価格を返すようにします。このように関数f（n）を書くだけです。

f（n）：=price [i] + f（n – i – 1）の最大値。ここで、iは0から（n – 1）の範囲です。

入力と出力

入力 ：

さまざまな長さの価格、およびロッドの長さ。ここでの長さは8です。

出力 ：

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

ロッドを長さ2と6にカットします。利益は5+17 =22

アルゴリズム

rodCutting(price, 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

例

#include <iostream>
using namespace std;

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

int rodCutting(int price[], int n) {    //from price and length of n, find max profit
   int profit[n+1];
   profit[0] = 0;
   int maxProfit;

   for (int i = 1; i<=n; i++) {
      maxProfit = INT_MIN;    //initially set as -ve infinity
      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