कार बेचकर अधिकतम लाभ प्राप्त करने का C++ प्रोग्राम

मान लीजिए लाल और नीली कारों की माँग है। एक ऑटोमोबाइल कंपनी p लाल कारें और q नीली कारें अलग-अलग कीमतों पर बेचने का फैसला करती है। वर्तमान में कंपनी के पास 'a' लाल कारें, '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 प्राप्त होगा। साथ ही, वे 180000 मूल्य की लाल कार बेच सकते हैं और 160000 और 150000 मूल्य की कारों को रंगकर कुल 490000 प्राप्त कर सकते हैं। कुल लाभ 610000 + 490000 = 1100000 होगा।

चरण

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

एक सरणी dp परिभाषित करें
सरणी A, B, C को सॉर्ट करें
i := 0 से p-1 तक:
    A[i] को dp के अंत में डालें
i := 0 से q-1 तक:
    B[i] को dp के अंत में डालें
dp सरणी को सॉर्ट करें
dp सरणी को उलट दें
i := 1 से dp के आकार-1 तक:
    dp[i] := dp[i] + dp[i-1]
tmp := 0
res := dp का अंतिम तत्व
i := 1 से min(c, p+q) तक:
    tmp := tmp + C[i-1]
    res := max(res, dp[p+q-i] + tmp)
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}