मान लीजिए हमारे पास एक 2D ग्रिड है जो एक कैंपस को दर्शाता है, जिसमें N वर्कर्स और M बाइक्स हैं, जहां N <= M। प्रत्येक वर्कर और बाइक इस ग्रिड पर 2D निर्देशांक में स्थित हैं। हमें प्रत्येक वर्कर को एक यूनिक बाइक असाइन करनी है ताकि प्रत्येक वर्कर और उनकी असाइन की गई बाइक के बीच मैनहट्टन दूरी का योग न्यूनतम हो।
हम जानते हैं कि दो बिंदुओं p1 और p2 के बीच मैनहट्टन दूरी है: (p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|। हमें प्रत्येक वर्कर और उनकी असाइन की गई बाइक के बीच मैनहट्टन दूरियों के न्यूनतम संभावित योग को ढूंढना है।
उदाहरण के लिए, यदि इनपुट है workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]] तो आउटपुट 6 होगा।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- एक फ़ंक्शन helper() परिभाषित करें। यह a,b लेगा
- return |a[0]-b[0]| + |a[1] - b[1]|
- एक फ़ंक्शन solve() परिभाषित करें। यह bikes, workers, bikev, i:= 0 लेगा
- info := i और bikev के साथ एक सूची
- यदि info मेमो में मौजूद है, तो
- memo[info] लौटाएं
- यदि i वर्कर्स के आकार के समान है, तो
- 0 लौटाएं
- temp := infinity
- j को 0 से bikes के आकार तक रेंज में, करें
- यदि bikev[j] नॉन-जीरो नहीं है, तो
- bikev[j]:= 1
- temp := temp का न्यूनतम, helper(workers[i], bikes[j]) + solve(bikes, workers, bikev, i+1)
- bikev[j]:= 0
- यदि bikev[j] नॉन-जीरो नहीं है, तो
- memo[info]:= temp
- temp लौटाएं
- एक फ़ंक्शन assignBikes() परिभाषित करें। यह workers, bikes लेगा
- bikev := एक सूची जिसका आकार bikes के आकार के समान है, इसे false से भरें
- memo:= एक नया मैप
- solve(bikes, workers, 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,bikev,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
