পাইথনে বাড়ি এবং নিকটতম মেলবক্সের মধ্যে সর্বনিম্ন মোট দূরত্ব খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি অ্যারে আছে যার নাম হাউসস এবং আরেকটি মান আছে k। এখানে বাড়িগুলি[i] একটি রাস্তার পাশে ith বাড়ির অবস্থানকে প্রতিনিধিত্ব করে, আমাদের রাস্তায় k মেলবক্সগুলি বরাদ্দ করতে হবে এবং প্রতিটি বাড়ি এবং এর নিকটতম মেলবক্সের মধ্যে সর্বনিম্ন মোট দূরত্ব খুঁজে বের করতে হবে৷

সুতরাং, যদি ইনপুটটি houses =[6,7,9,16,22] k =2 এর মত হয়, তাহলে আউটপুট হবে 9 কারণ যদি আমরা 7 এবং 18 এ মেইলবক্স রাখি, তাহলে প্রতিটি বাড়ি থেকে সর্বনিম্ন মোট দূরত্ব হবে |6 -7|+|7-7|+|9-7|+|16- 18|+|22-18| =1+0+2+2+4 =9.

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

তালিকা ঘর সাজান
একটি ফাংশন util() সংজ্ঞায়িত করুন। এটি idx, n, k
লাগবে
k যদি 1 এর মত হয়, তাহলে
- কোর :=ঘর [(n + idx)/2]
  এর ভাগফল
- [|হাউস[i] - কোর| এর সমস্ত উপাদানের যোগফল ফেরত দিন আইডিএক্স থেকে n])
  পরিসরের প্রতিটি i এর জন্য
ফলাফল:=অসীম
আইডিএক্স থেকে n রেঞ্জের জন্য, করুন
- যদি n - i
  - লুপ থেকে বেরিয়ে আসুন
- ফলাফল :=ন্যূনতম ফলাফল এবং util(idx, i, 1) + util(i+1, n, k - 1)
ফেরত ফলাফল
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন:
রিটার্ন ইউটিল (0, বাড়ির আকার - 1, কে)

উদাহরণ

আসুন আরও ভালভাবে বোঝার জন্য নিম্নলিখিত বাস্তবায়ন দেখি

def solve(houses, k):
   houses.sort()
   def util(idx, n, k):
      if k == 1:
         core = houses[(n + idx) // 2]
         return sum([abs(houses[i] - core) for i in range(idx, n + 1)])
      result = float('inf')
      for i in range(idx, n + 1):
         if n - i < k - 1:
            break
         result = min(result, util(idx, i, 1) + util(i+1, n, k - 1))
      return result
   return util(0, len(houses) - 1, k)

houses = [6,7,9,16,22]
k = 2
print(solve(houses, k))

ইনপুট

[6,7,9,16,22], 2