मान लीजिए हमारे पास एक 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]|
-
-
फ़ंक्शन को हल करें () को परिभाषित करें। यह ले जाएगा बाइक, कार्यकर्ता,bikev,i:=0
-
जानकारी :=i और Bikev के साथ एक सूची
-
अगर मेमो में जानकारी मौजूद है, तो
-
वापसी ज्ञापन [जानकारी]
-
-
अगर मैं श्रमिकों के आकार के समान हूं, तो
-
वापसी 0
-
-
अस्थायी:=अनंत
-
j के लिए 0 से लेकर बाइक के आकार तक, करें
-
यदि नहीं Bikev[j] गैर-शून्य है, तो
-
बाइकव [जे]:=1
-
अस्थायी:=न्यूनतम अस्थायी, सहायक (श्रमिक [i], बाइक [जे]) + हल (बाइक, श्रमिक, बाइकव, i+1)
-
बाइकव [जे]:=0
-
-
-
ज्ञापन [जानकारी]:=अस्थायी
-
वापसी अस्थायी
-
एक फ़ंक्शन असाइनबाइक () को परिभाषित करें। यह श्रमिकों, बाइकों को ले जाएगा
-
Bikev :=एक सूची जिसका आकार बाइक के आकार के समान है, इसे असत्य से भरें
-
ज्ञापन:=एक नया नक्शा
-
रिटर्न सॉल्व (बाइक, वर्कर, बाइकव)
उदाहरण
आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -
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