通过在C ++中切割不同长度的杆来寻找最大利润的程序

假设我们有一个长度为n的杆。我们还有一个列表，其中包含不同的尺寸和每种尺寸的价格。我们必须通过切割杆并在市场上出售来找到最高价格。通过在不同位置进行切割并在切割杆后比较价格来获得最佳价格。

因此，如果输入像价格= [1、5、8、9、10、17、17、20]，n = 8，则输出为22，例如通过将杆的长度切成2和6。利润是5 + 17 = 22。

为了解决这个问题，我们将遵循以下步骤-

• 定义大小为n + 1的数组利润。

• 利润[0]：= 0

• 对于初始化i：= 1，当i <= n时，更新（将i增加1），-

• maxProfit：= maxProfit和价格[j] +利润[i − j − 1]的最大值

• maxProfit：=负无穷大

• 对于初始化j：= 0，当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