इस समस्या में, हमें n तत्वों का एक ऐरे दिया गया है। ऐरे का प्रत्येक तत्व या तो एक पुलिसकर्मी या एक चोर है, एक चोर को एक पुलिसकर्मी पकड़ सकता है और हमें पुलिसकर्मियों द्वारा पकड़े जा सकने वाले चोरों की अधिकतम संख्या ज्ञात करनी है यदि एक पुलिसकर्मी अपने से k यूनिट दूर चोर को पकड़ सकता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट -
ऐरे = {T, P, P, P, T, T, T} K = 2.
आउटपुट - 3
व्याख्या - यहां, प्रत्येक पुलिसकर्मी एक चोर पकड़ेगा,
इंडेक्स 1 पर P इंडेक्स 0 पर T को पकड़ेगा। इंडेक्स 2 पर P इंडेक्स 4 पर T को पकड़ेगा। इंडेक्स 3 पर P इंडेक्स 5 पर T को पकड़ेगा।
यह अनुमत है क्योंकि पुलिसकर्मी उन चोरों को पकड़ सकते हैं जो उनसे दूरी 2 पर हैं।
इस समस्या को हल करने के लिए, हम लालची एल्गोरिदम का उपयोग करेंगे। यह दो तरीकों से काम कर सकता है, या तो पुलिसकर्मी के निकटतम सभी चोरों को पकड़ें या पुलिसकर्मी से सबसे दूर चोरों को पकड़ें। लेकिन दोनों मामलों में, सबसे इष्टतम समाधान नहीं मिलता क्योंकि दोनों कुछ ऐसे मामलों में पीछे रह जाते हैं जहां एक पुलिसकर्मी को एक निश्चित दूरी पर चोर को पकड़ना होता है।
तो, निम्नलिखित एक एल्गोरिदम है जो सबसे आशाजनक परिणाम प्रदान करता है,
हम पहले पुलिसकर्मी और चोर के इंडेक्स के साथ शुरू करेंगे। यदि |index(P1) - index(T1)| <= k, तो चोर पकड़ा जा सकता है और हम अगले पुलिस-चोर जोड़े की जांच करेंगे। अन्यथा, हम min(p,t) बढ़ाएंगे और पुलिस और चोर के अगले इंडेक्स की जांच करेंगे। यह जांच तब तक की जाएगी जब तक सभी पुलिसकर्मी और चोर जांचे नहीं जाते और अंत में पकड़े गए चोरों की संख्या प्रिंट की जाती है।
उदाहरण
हमारे एल्गोरिदम का चित्रण करने वाला प्रोग्राम,
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int policeThief(char arr[], int n, int k) {
int caught = 0;
vector<int> thieves;
vector<int> policemen;
for (int i = 0; i < n; i++) {
if (arr[i] == 'P')
policemen.push_back(i);
else if (arr[i] == 'T')
thieves.push_back(i);
}
int thief = 0, police = 0;
while (thief < thieves.size() && police < policemen.size()) {
if (abs(thieves[thief] - policemen[police]) <= k) {
caught++;
thief++;
police++;
} else if (thieves[thief] < policemen[police])
thief++;
else
police++;
}
return caught;
}
int main() {
int k, n;
char arr2[] = {'P', 'T', 'T', 'P', 'P', 'T', 'T', 'T', 'T', 'P'};
k = 2;
n = sizeof(arr2) / sizeof(arr2[0]);
cout << "पुलिस द्वारा पकड़े जा सकने वाले चोरों की अधिकतम संख्या है :" << policeThief(arr2, n, k);
return 0;
}
आउटपुट
पुलिस द्वारा पकड़े जा सकने वाले चोरों की अधिकतम संख्या है :4
