এই সমস্যায়, আমাদের n উপাদানগুলির একটি অ্যারে দেওয়া হয়েছে। অ্যারের প্রতিটি উপাদানে একজন পুলিশ বা একজন চোর থাকে, একজন চোরকে একজন পুলিশ ধরে ফেলতে পারে এবং একজন পুলিশ তার থেকে একজন চোর কে ইউনিট দূরে ধরতে পারলে আমাদের সর্বাধিক সংখ্যক চোরকে পুলিশ ধরতে পারে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,
ইনপুট৷ −
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)| <=কে, চোর ধরা যেতে পারে এবং আমরা পরবর্তী পুলিশ-চোর জুটির জন্য পরীক্ষা করব। অন্যথায়, আমরা 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
