मान लीजिए हमारे पास N तत्वों वाला एक ऐरे A है। एक अन्य संख्या T है। मान लें अमल एक प्रोग्रामिंग प्रतियोगिता में भाग लेने की कोशिश कर रहा है। यह T मिनट तक चलती है और N समस्याएं हैं। उसे iवीं समस्या को हल करने में A[i] समय लगता है। वह N समस्याओं में से शून्य या अधिक समस्याओं को हल करने के लिए चुनेगा, ताकि उन्हें हल करने में कुल मिलाकर T मिनट से अधिक न लगे। हमें उसकी पसंद की समस्याओं को हल करने में लगने वाला सबसे लंबा संभव समय ढूंढना है।
उदाहरण के लिए, यदि इनपुट T = 17; A = [2, 3, 5, 7, 11] है, तो आउटपुट 17 होगा, क्योंकि यदि वह पहली चार समस्याओं को चुनता है, तो उसे उन्हें हल करने में कुल 2 + 3 + 5 + 7 = 17 मिनट लगते हैं, जो T मिनट से अधिक नहीं होने वाला सबसे लंबा संभव समय है।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
n := A का आकार आकार (n / 2) का एक ऐरे b और आकार (n - n/2) का c परिभाषित करें i := 0 से n/2-1 तक, करें: b[i] := A[i] i := n/2 से n-1 तक, करें: c[i - n/2] = A[i] ऐरे B, C परिभाषित करें bit := 0 से 2^(n/2)-1 तक, करें: p := 0 i := 0 से n/2-1 तक, करें: यदि bit AND 2^i शून्येतर है, तो p := p + b[i] p को B के अंत में डालें bit := 0 से 2^(n - n/2)-1 तक, करें: p := 0 i := 0 से n - n/2-1 तक, करें: यदि bit AND 2^i शून्येतर है, तो p := p + c[i] p को C के अंत में डालें mx := 0 ऐरे C को सॉर्ट करें i := 0 से B के आकार-1 तक, करें: यदि t - B[i] < 0, तो: अगले पुनरावृत्ति पर जाएं itr = C में (t - B[i]) से बड़ा अगला तत्व itr घटाएं mx := mx और (itr + B[i]) का अधिकतम 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
