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 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

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}