সমস্ত সমস্যা সমাধানের জন্য T-এর চেয়ে বেশি নয় দীর্ঘতম সম্ভাব্য সময় খুঁজে পেতে C++ প্রোগ্রাম

ধরুন আমাদের কাছে N উপাদান সহ একটি অ্যারে রয়েছে। আর একটি নম্বর T আছে। বিবেচনা করুন অমল একটি প্রোগ্রামিং প্রতিযোগিতায় অংশগ্রহণ করার চেষ্টা করছে। এটি T মিনিটের জন্য স্থায়ী হয় এবং N সমস্যাগুলি উপস্থিত করে। সমস্যা সমাধানের জন্য তার কাছে A[i] সময় আছে। তিনি N সমস্যাগুলি থেকে সমাধান করার জন্য শূন্য বা তার বেশি সমস্যা বেছে নেবেন, যাতে সেগুলি সমাধান করতে মোট T মিনিট আর লাগে না। তার পছন্দের সমস্যার সমাধান করতে আমাদের সবচেয়ে দীর্ঘ সম্ভাব্য সময় খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট টি =17 এর মত হয়; A =[2, 3, 5, 7, 11], তাহলে আউটপুট হবে 17, কারণ সে যদি প্রথম চারটি সমস্যা বেছে নেয়, তাহলে সেগুলি সমাধান করতে তার মোট সময় লাগে 2 + 3 + 5 + 7 =17 মিনিট, যা টি মিনিটের বেশি নয় সম্ভাব্য দীর্ঘতম সময়।

পদক্ষেপ

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

n := size of A
Define an array b of size (n / 2) and c of size (n - n/2)
for initialize i := 0, when i < n / 2, update (increase i by 1), do:
   b[i] := A[i]
for initialize i := n / 2, when i < n, update (increase i by 1), do:
   c[i - n / 2] = A[i]
Define an array B, C
for bit in range 0 to 2^(n/2), increase bit after each iteration, do
   p := 0
   for initialize i := 0, when i < n / 2, update (increase i by 1), do:
      if bit AND 2^i is non zero, then
         p := p + b[i]
   insert p at the end of B
for bit in range 0 to 2^(n - n/2), increase bit after each iteration
   p := 0
   for initialize i := 0, when i < n - n / 2, update (increase i by 1), do:
      if bit AND 2^i is non-zero, then
         p := p + c[i]
   insert p at the end of C
mx := 0
sort the array C
for initialize i := 0, when i < size of B, update (increase i by 1), do:
   if t - B[i] < 0, then:
      Ignore following part, skip to the next iteration
   itr = next larger element of (t - B[i]) in C
   (decrease itr by 1)
   mx := maximum of mx and (itr + B[i])
return mx

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;

int solve(int t, vector<int> A){
   int n = A.size();
   vector<int> b(n / 2), c(n - n / 2);
   for (int i = 0; i < n / 2; i++)
      b[i] = A[i];
   for (int i = n / 2; i < n; i++)
      c[i - n / 2] = A[i];
   vector<int> B, C;
   for (int bit = 0; bit < (1 << (n / 2)); bit++){
      int p = 0;
      for (int i = 0; i < n / 2; i++){
         if (bit & (1 << i))
            p += b[i];
      }
      B.push_back(p);
   }
   for (int bit = 0; bit < (1 << (n - n / 2)); bit++){
      int p = 0;
      for (int i = 0; i < n - n / 2; i++){
         if (bit & (1 << i))
            p += c[i];
      }
      C.push_back(p);
   }
   int mx = 0;
   sort(C.begin(), C.end());
   for (int i = 0; i < B.size(); i++){
      if (t - B[i] < 0)
         continue;
      auto itr = upper_bound(C.begin(), C.end(), t - B[i]);
      itr--;
      mx = max(mx, *itr + B[i]);
   }
   return mx;
}
int main(){
   int T = 17;
   vector<int> A = { 2, 3, 5, 7, 11 };
   cout << solve(T, A) << endl;
}

ইনপুট

17, { 2, 3, 5, 7, 11 }

আউটপুট

17