자동차 판매로 얻을 수 있는 최대 금액을 알아내는 C++ 프로그램

<시간/>

빨간색 및 파란색 자동차 판매에 대한 수요가 있다고 가정합니다. 한 자동차 회사에서 p개의 빨간색 자동차와 q개의 파란색 자동차를 서로 다른 가격으로 판매하기로 결정했습니다. 현재 이 회사는 빨간색 차 '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, 200000 가치의 파란색 자동차를 판매하고 가치 210000의 자동차를 파란색으로 칠할 수 있습니다. 파란색 자동차를 판매하여 얻은 총 가치는 610000입니다. 또한 가치가 18000인 빨간색 자동차와 가치가 160000 및 150000인 페인트 자동차를 판매하여 총 490000을 얻을 수 있습니다. 획득한 총 이익 가치는 610000 + 490000 =1100000입니다. /P>

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

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}