数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究切割棒材
给定一根长度为 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+ 浏览量
广告