মান লিজিয়ে, লাল এবং নীল গাড়ির চাহিদা আছে। একটি অটোমোবাইল কোম্পানি 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।
কোম্পানি ২০০০০০, ২০০০০০ দামের নীল গাড়ি এবং ২১০০০০ দামের গাড়ি নীল রঙ করে বিক্রি করতে পারে। নীল গাড়ি থেকে মোট ৬১০০০০ লাভ হবে। আর লাল গাড়ি ১৮০০০০ দামে এবং ১৬০০০০, ১৫০০০০ দামের গাড়ি লাল রঙ করে বিক্রি করলে মোট ৪৯০০০০ লাভ হবে। মোট লাভ = ৬১০০০০ + ৪৯০০০০ = ১১০০০০০।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
dp অ্যারে সংজ্ঞায়িত করুন A, B, C অ্যারে সোর্ট করুন i := 0 থেকে p-1 পর্যন্ত: dp-র শেষে A[i] যোগ করুন i := 0 থেকে q-1 পর্যন্ত: dp-র শেষে B[i] যোগ করুন dp অ্যারে সোর্ট করুন dp অ্যারে রিভার্স করুন i := 1 থেকে dp-র আকার-১ পর্যন্ত: 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) 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} আউটপুট
1100000
