資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式：計算銷售汽車所能獲得的最大收益
假設，市場對紅色和藍色汽車有需求。一家汽車公司決定出售p輛紅色汽車和q輛藍色汽車，每輛汽車價格不同。目前，該公司庫存中有'a'輛紅色汽車，'b'輛藍色汽車和'c'輛無色汽車（尚未噴漆）。不同汽車的價值儲存在陣列A、B和C中。因此，該公司需要在一天內出售p + q輛汽車，並希望從中獲得最大利潤。無色汽車可以噴成任何顏色，紅色或藍色。我們需要找出銷售汽車所能獲得的最大利潤。
例如，如果輸入為p = 3，q = 3，a = 3，b = 3，c = 2，A = {150000, 200000, 200000}，B = {150000, 120000, 180000}，C = {210000, 160000, 150000}，則輸出為1100000。
該公司可以出售價值200000的藍色汽車，並將價值210000的無色汽車噴成藍色。出售藍色汽車總共獲得610000的收益。此外，他們可以出售價值180000的紅色汽車，並將價值160000和150000的無色汽車噴成紅色，總共獲得490000的收益。獲得的總利潤為610000 + 490000 = 1100000。
為了解決這個問題，我們將遵循以下步驟：
Define an array dp sort the arrays A, B, and C for initialize i := 0, when i < p, update (increase i by 1), do: insert A[i] at the end of dp for initialize i := 0, when i < q, update (increase i by 1), do: insert B[i] at the end of dp sort the array dp reverse the array dp for initialize i := 1, when i < size of dp, update (increase i by 1), do: dp[i] := dp[i] + dp[i - 1] tmp := 0 res := last element of dp for initialize i := 1, when i < (minimum of (c and p +q), update (increase i by 1), do: tmp := tmp + C[i - 1] res := maximum of (res and dp[p + q - i] + tmp) return res
示例
讓我們看看下面的實現來更好地理解：
#include <bits/stdc++.h>
using namespace std;
int solve(int p, int q, int a, int b, int c, vector<int> A, vector<int> B, vector<int> C){
vector<int> dp(1, 0);
sort(A.rbegin(), A.rend());
sort(B.rbegin(), B.rend());
sort(C.rbegin(), C.rend());
for(int i = 0; i < p; ++i)
dp.push_back(A[i]);
for(int i = 0; i < q; ++i)
dp.push_back(B[i]);
sort(dp.begin(), dp.end());
reverse(dp.begin() + 1, dp.end());
for(int i = 1; i < (int)dp.size(); ++i)
dp[i] += dp[i - 1];
int tmp = 0;
int res = dp.back();
for(int i = 1; i <= min(c, p + q); ++i) {
tmp += C[i - 1];
res = max(res, dp[p + q - i] + tmp);
}
return res;
}
int main() {
int p = 3, q = 3, a = 3, b = 3, c = 2;
vector<int> A = {150000, 200000, 200000}, B = {150000, 120000, 180000}, C = {210000, 160000, 150000};
cout<< solve(p, q, a, b, c, A, B, C);
return 0;
}輸入
3, 3, 3, 3, 2, {150000, 200000, 200000}, {150000, 120000, 180000}, {210000, 160000, 150000}輸出
1100000
更新於: 2022年3月2日
233 次檢視
廣告