資料結構
網路
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 次檢視
廣告