数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
广告