数据结构
网络
关系型数据库管理系统
操作系统
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
更新于： 2020-06-17
5K+ 浏览
广告