পাইথনে ক্যাম্পাস বাইক II

ধরুন আমাদের একটি 2D গ্রিড আছে, যা একটি ক্যাম্পাসের প্রতিনিধিত্ব করে, সেখানে N কর্মী এবং M বাইক রয়েছে, N <=M এর মান। এখন প্রতিটি কর্মী এবং বাইক এই গ্রিডে একটি 2D সমন্বয়ে রয়েছে। সুতরাং, আমরা যদি প্রতিটি কর্মীকে একটি অনন্য বাইক বরাদ্দ করতে চাই যাতে প্রতিটি কর্মী এবং তাদের নির্ধারিত বাইকের মধ্যে ম্যানহাটনের দূরত্বের যোগফল ন্যূনতম হয়৷

আমরা জানি যে দুটি বিন্দু p1 এবং p2 এর মধ্যে ম্যানহাটনের দূরত্ব হল (p1, p2) =|p1.x - p2.x| + |p1.y - p2.y|। আমাদের প্রতিটি কর্মী এবং তাদের নির্ধারিত বাইকের মধ্যে ম্যানহাটনের ন্যূনতম সম্ভাব্য দূরত্ব খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট শ্রমিকদের মত হয় =[[0,0],[2,1]], বাইক =[[1,2],[3,3]]

তাহলে আউটপুট হবে 6

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন সাহায্যকারী () সংজ্ঞায়িত করুন। এটি a,b

  লাগবে

  • ফেরত |a[0]-b[0]| + |a[1] - b[1]|

• একটি ফাংশন সমাধান () সংজ্ঞায়িত করুন। এটি বাইক, শ্রমিক, বাইকেভ, i:=0

  লাগবে

• তথ্য :=i এবং বাইকেভ সহ একটি তালিকা

• যদি তথ্য মেমোতে উপস্থিত থাকে, তাহলে

  • ফেরত মেমো[তথ্য]

• যদি আমি কর্মীদের আকারের সমান হয়, তাহলে

  • রিটার্ন 0

• তাপমাত্রা :=অসীম

• j রেঞ্জ 0 থেকে বাইকের আকারের জন্য, করুন

  • যদি বাইকেভ[জে] অ-শূন্য হয়, তাহলে

    • বাইকেভ[জে]:=1

    • temp :=সর্বনিম্ন টেম্প, হেল্পার(কর্মী[i], বাইক[j]) +সমাধান (বাইক, শ্রমিক, বাইকেভ, i+1)

    • বাইকেভ[জে]:=0

• মেমো[তথ্য]:=তাপমাত্রা

• রিটার্ন টেম্প

• একটি ফাংশন assignBikes() সংজ্ঞায়িত করুন। এতে শ্রমিক, বাইক লাগবে

• বাইকেভ :=একটি তালিকা যার আকার বাইকের আকারের সমান, এটিকে মিথ্যা দিয়ে পূরণ করুন

• মেমো:=একটি নতুন মানচিত্র

• রিটার্ন সলভ (বাইক, শ্রমিক, বাইকেভ)

উদাহরণ

আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -

class Solution(object):
   def helper(self,a,b):
      return abs( (a[0]-b[0]) ) + abs( (a[1] - b[1]) )
   def solve(self,bikes,workers,bikev,i=0):
      info = (i,tuple(bikev))
      if info in self.memo:
         return self.memo[info]
      if i == len(workers):
         return 0
      temp = float('inf')
      for j in range(len(bikes)):
         if not bikev[j]:
            bikev[j]=1
            temp = min(temp,self.helper(workers[i],bikes[j])+self.solve(bikes,workers,bi
kev,i+1))
            bikev[j]=0
      self.memo[info]= temp
      return temp
   def assignBikes(self, workers, bikes):
      bikev = [False for i in range(len(bikes))]
      self.memo={}
      return self.solve(bikes,workers,bikev)
ob = Solution()
print(ob.assignBikes([[0,0],[2,1]],[[1,2],[3,3]]))

ইনপুট

[[0,0],[2,1]] [[1,2],[3,3]]

আউটপুট

6