通过在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