গাড়ি বিক্রি করে সর্বোচ্চ কত টাকা আয় করা যায় তা খুঁজে বের করতে C++ প্রোগ্রাম

ধরা যাক, বিক্রির জন্য লাল ও নীল রঙের গাড়ির চাহিদা রয়েছে। একটি অটোমোবাইল কোম্পানি বিভিন্ন দামের p লাল গাড়ি এবং q নীল গাড়ি বিক্রি করার সিদ্ধান্ত নেয়। বর্তমানে, কোম্পানির কাছে 'ক' নম্বর লাল রঙের গাড়ি, 'বি' নম্বরের নীল রঙের গাড়ি এবং 'গ' নম্বরের বর্ণহীন গাড়ি রয়েছে (গাড়িগুলো এখনও রং করা হয়নি)। বিভিন্ন গাড়ির মান 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 + 4901000<=49010000। /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}