पायथन में घर और निकटतम मेलबॉक्स के बीच न्यूनतम कुल दूरी खोजने का कार्यक्रम

मान लीजिए कि हमारे पास घरों नामक एक सरणी है और एक और मूल्य k है। यहां मकान [i] सड़क के किनारे ith घर के स्थान का प्रतिनिधित्व करते हैं, हमें गली में k मेलबॉक्स आवंटित करने होंगे, और प्रत्येक घर और उसके निकटतम मेलबॉक्स के बीच न्यूनतम कुल दूरी ज्ञात करनी होगी।

इसलिए, यदि इनपुट घरों की तरह है =[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.

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• सूची घरों को क्रमबद्ध करें

• उपयोग() फ़ंक्शन को परिभाषित करें। यह idx, n, k

  . लेगा

• अगर k 1 के समान है, तो

  • कोर:=मकान [(n + idx)/2 का भागफल]

  • [|घरों[i] - कोर| . के सभी तत्वों का रिटर्न योग idx से n तक की श्रेणी में प्रत्येक i के लिए])

• परिणाम:=अनंत

• idx से n तक की श्रेणी में i के लिए, करें

  • अगर n - i

    • लूप से बाहर आएं

  • परिणाम:=न्यूनतम परिणाम और उपयोग (idx, i, 1) + उपयोग (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

आउटपुट

9