Chương trình C ++ để tìm ra số tiền tối đa có thể kiếm được từ việc bán ô tô

Giả sử, có một nhu cầu về ô tô màu đỏ và màu xanh lam để bán. Một công ty ô tô quyết định bán p ô tô màu đỏ và q ô tô màu xanh với giá khác nhau. Hiện tại, công ty có một số lượng xe màu đỏ, số lượng xe ô tô màu xanh và số lượng xe ô tô màu 'c' (những chiếc xe chưa được sơn) trong kho của họ. Giá trị của những chiếc xe khác nhau được cho trong mảng A, B và C. Vì vậy, công ty phải bán p + q số xe trong một ngày và họ phải thu được lợi nhuận tối đa từ chúng. Những chiếc xe không màu có thể được sơn bất kỳ màu nào, đỏ hoặc xanh. Chúng tôi tìm ra mức lợi nhuận tối đa có thể đạt được từ việc bán ô tô.

Vì vậy, nếu đầu vào là p =3, q ​​=3, a =3, b =3, c =2, A ={150000, 200000, 200000}, B ={150000, 120000, 180000}, C ={ 210000, 160000, 150000}, thì đầu ra sẽ là 1100000.

Công ty có thể bán xe ô tô màu xanh lam trị giá 200000, 200000 và sơn xe ô tô trị giá 210000 thành màu xanh lam. Tổng giá trị thu được từ việc bán ô tô màu xanh sẽ là 610000. Ngoài ra, họ có thể bán ô tô màu đỏ trị giá 18000 và sơn ô tô có giá trị 160000 và 150000 để thu được tổng cộng 490000. Tổng giá trị lợi nhuận thu được sẽ là 610000 + 490000 =1100000.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

3, 3, 3, 3, 2, {150000, 200000, 200000}, {150000, 120000, 180000}, {210000, 160000, 150000}

Đầu ra

1100000