সমস্যা বিবরণ
একটি ২D গ্রিড যা ক্যাম্পাসকে প্রতীকী করছে। এখানে N জন কর্মী এবং Mটি বাইক আছে (N ≤ M)। প্রতিটি কর্মী ও বাইকের ২D কোঅর্ডিনেট দেওয়া আছে। প্রতিটি কর্মীকে একটি অনন্য বাইক এসাইন করতে হবে যাতে সকল কর্মী ও তাদের বাইকের ম্যানহ্যাটান দূরত্বের যোগফল ন্যূনতম হয়।
ম্যানহ্যাটান দূরত্ব: |p1.x - p2.x| + |p1.y - p2.y|
উদাহরণ
ইনপুট: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
আউটপুট: 6
সমাধানের পদ্ধতি
এটি একটি ক্লাসিক অ্যাসাইনমেন্ট প্রობ্লেম (Assignment Problem) যা ব্যাকট্র্যাকিং + মেমোইজেশন (DP with Bitmask) দিয়ে সমাধান করা হয়।
অ্যালগরিদম
helper(a, b)ফাংশন দিয়ে ম্যানহ্যাটান দূরত্ব ক্যালকুলেট করুনsolve(bikes, workers, bikev, i)রিকার্সিভ ফাংশন:bikev= বাইক ব্যবহৃত হয়েছে কিনা ট্র্যাক করার বুলিয়ান অ্যারেi= বর্তমান কর্মীর ইনডেক্স- মেমোইজেশন কী:
(i, tuple(bikev)) - বেস কেস: সব কর্মী এসাইন হলে ০ রিটার্ন
- প্রতিটি অনব্যবহৃত বাইক চেষ্টা করুন এবং ন্যূনতম খুঁজুন
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, bikev, i+1))
bikev[j] = 0
self.memo[info] = temp
return temp
def assignBikes(self, workers, bikes):
bikev = [False for _ 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]])) # আউটপুট: 6
জটিলতা বিশ্লেষণ
- সময় জটিলতা: O(N × M × 2^M) — N = কর্মী, M = বাইক
- স্থান জটিলতা: O(N × 2^M) — মেমোইজেশন টেবিলের জন্য
মূল বিষয়বস্তু
- বিটমাস্ক DP ব্যবহার করে স্টেট কंপ্রেশন
- ছোট ইনপুট সাইজের জন্য ব্যাকট্র্যাকিং কার্যকর
- বড় ইনপুটের জন্য হাঙ্গেরিয়ান অ্যালগরিদম (O(N³)) ভালো
