इस समस्या में, हमें n तत्वों की एक सरणी दी गई है। सरणी के प्रत्येक तत्व में या तो एक पुलिसकर्मी या चोर होता है, एक चोर को एक पुलिस द्वारा पकड़ा जा सकता है और हमें चोरों की अधिकतम संख्या का पता लगाना होगा जो पुलिस द्वारा पकड़ी जा सकती है यदि कोई पुलिसकर्मी चोर k इकाइयों को उससे दूर पकड़ सकता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट -
array = {T, P, P, P, T , T, T}
K = 2. आउटपुट -3
स्पष्टीकरण - यहां हर पुलिसकर्मी चोर को पकड़ेगा,
P at index 1 will catch T at index 0. P at index 2 will catch T at index 4. P at index 3 will catch T at index 5.
इसकी अनुमति है क्योंकि पुलिसकर्मी उन चोरों को पकड़ सकते हैं जो उनसे 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 << "Maximum number of thieves that can be caught by police is :"<<policeThief(arr2, n, k);
return 0;
} आउटपुट
Maximum number of thieves that can be caught by police is :4