सी ++ प्रोग्राम सभी समस्याओं को हल करने के लिए टी से अधिक नहीं सबसे लंबे समय तक संभव समय खोजने के लिए

मान लीजिए कि हमारे पास एन तत्वों के साथ एक सरणी ए है। एक और नंबर टी लें। विचार करें कि अमल एक प्रोग्रामिंग प्रतियोगिता में भाग लेने की कोशिश कर रहा है। यह टी मिनट तक रहता है और एन समस्याएं पेश करता है। उसके पास ith समस्या को हल करने के लिए A[i] समय है। वह N समस्याओं में से हल करने के लिए शून्य या अधिक समस्याओं का चयन करेगा, ताकि उन्हें हल करने में कुल T मिनट न लगे। हमें उसकी पसंद की समस्याओं को हल करने में सबसे लंबा संभव समय निकालना होगा।

तो, अगर इनपुट टी =17 की तरह है; ए =[2, 3, 5, 7, 11], तो आउटपुट 17 होगा, क्योंकि यदि वह पहली चार समस्याओं को चुनता है, तो उसे हल करने में कुल मिलाकर 2 + 3 + 5 + 7 =17 मिनट लगते हैं, जो सबसे लंबा संभव समय है जो T मिनट से अधिक न हो।

कदम

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

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