資料結構
網路
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+ 瀏覽量
廣告