杆切割

杆的长度为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