資料結構
網路
關係型資料庫管理系統
作業系統
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+ 瀏覽
廣告