杆切割
杆的长度为n。还提供了另一个表格，其中包含不同的尺寸和每种尺寸的价格。通过切割杆并在市场上出售来确定最高价格。
通过在不同位置进行切割并在切割杆后比较价格来获得最佳价格。
让f(n)在切成长度为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