車を売ることで稼ぐことができる最大の金額を見つけるためのC++プログラム

赤と青の車の販売需要があるとします。自動車会社は、異なる価格のp個の赤い車とq個の青い車を販売することにしました。現在、同社は「a」の数の赤い車、「b」の数の青い車、および「c」の数の無色の車（車はまだ塗装されていません）を在庫しています。さまざまな車の値は配列A、B、Cで示されます。したがって、会社は1日に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、200000の青い車を販売し、価値210000の車を青に塗ることができます。青い車を売って得られる合計値は610000になります。また、値18000の赤い車を販売し、値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