数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 程序：查找切割不同长度木棒以获得最大利润
假设我们有一根长度为 n 的木棒。我们还有一个列表，其中包含每种尺寸的不同尺寸和价格。我们必须通过切割木棒并在市场上出售它们来找到最高价格。通过在不同位置切割木棒并比较切割后木棒的价格来获得最佳价格。
因此，如果输入类似于 prices = [1, 5, 8, 9, 10, 17, 17, 20]，n = 8，则输出将为 22，因为通过将木棒切割成长度 2 和 6。利润为 5 + 17 = 22。
为了解决这个问题，我们将遵循以下步骤：
定义一个大小为 n+1 的数组 profit。
profit[0] := 0
初始化 i := 1，当 i <= n 时，更新（i 增加 1），执行：
maxProfit := 负无穷大
初始化 j := 0，当 j < i 时，更新（j 增加 1），执行：
maxProfit := maxProfit 和 price[j] + profit[i − j − 1] 中的最大值
profit[i] := maxProfit
返回 maxProfit
让我们看看以下实现以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
int max(int a, int b) {
return (a > b)? a : b;
}
int rodCutting(int price[], int n) {
int profit[n+1];
profit[0] = 0;
int maxProfit;
for (int i = 1; i<=n; i++) {
maxProfit = INT_MIN;
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 << rodCutting(priceList, rodLength);
}输入
{1, 5, 8, 9, 10, 17, 17, 20}, 8输出
22
更新于： 2020年10月21日
644 次查看
广告