切割棒材

给定一根长度为 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

更新于: 17-6-2020

6K+ 浏览量

开启您的职业生涯

完成课程，获取认证

开始
广告