C++で異なる長さのロッドを切断することによって最大の利益を見つけるためのプログラム

長さnのロッドがあるとします。サイズごとに異なるサイズと価格を含むリストもあります。ロッドを切って市場で売って最高価格を見つけなければなりません。さまざまな位置でカットし、ロッドをカットした後の価格を比較することで、最良の価格を得るには。

したがって、入力がprices =[1、5、8、9、10、17、17、20]、n =8のようである場合、ロッドを長さ2および6に切断することにより、出力は22になります。利益は5+17=22です。

これを解決するには、次の手順に従います-

• サイズの配列利益を定義します：n+1。

• 利益[0]：=0

• 初期化i：=1の場合、i <=nの場合、更新（iを1増やします）、実行-

  • maxProfit：=負の無限大

  • 初期化j：=0の場合、j

    • maxProfit：=maxProfitと価格の最大値[j]+利益[i− j − 1]

  • 利益[i]：=maxProfit

• maxProfitを返す

理解を深めるために、次の実装を見てみましょう-

例

#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