Question Solved1 Answer Given an array of size n that has the following specifications: • each element in the array contains either a policeman or a thief. • each policeman can catch only one thief. a policeman cannot catch a thief who is more than K units away from the policeman (10p) Devise a greedy algorithm that finds the maximum number of thieves that can be caught. (20p) Prove that your algorithm satisfies the greedy-choice property.

DBPCFA The Asker · Computer Science

Transcribed Image Text: Given an array of size n that has the following specifications: • each element in the array contains either a policeman or a thief. • each policeman can catch only one thief. a policeman cannot catch a thief who is more than K units away from the policeman (10p) Devise a greedy algorithm that finds the maximum number of thieves that can be caught. (20p) Prove that your algorithm satisfies the greedy-choice property.
More
Transcribed Image Text: Given an array of size n that has the following specifications: • each element in the array contains either a policeman or a thief. • each policeman can catch only one thief. a policeman cannot catch a thief who is more than K units away from the policeman (10p) Devise a greedy algorithm that finds the maximum number of thieves that can be caught. (20p) Prove that your algorithm satisfies the greedy-choice property.
See Answer
Add Answer +20 Points
Community Answer
VULUOJ The First Answerer
See all the answers with 1 Unlock
Get 4 Free Unlocks by registration

(10p) device a greedy algorithm that finds the maximum number of theives that can be caught (20p) Prove that your algorithm satisfies the greedy-choice property. ANSWER: Python Programming:(Solution using Greedy Algorithm) def policeThief(arr,n,k):      i=0;      l=0;      r=0;      res=0;      thi = []      pol = [] #store indices in list      while i<n:           if arr[i] == 'P':                pol.append(i)           elif arr[i] == 'T':                thi.append(i)           i+ = 1 # track lowest current indices of # thief : thi[l], police : pol[r]       while l < len(thi) and r < len(pol): # can be caught           if(abs(thi[l]- pol[r]) <= k                res += 1                l+= 1               r+= 1 #increment the minimum index           elif thi[l] - pol[r]:                l+= 1           else:               r+= 1      return res # Driver Program if__name__=='__main__':      arrr1 = ['P', 'T', 'T', 'P', 'T' ... See the full answer