पायथन में घरों की पेंटिंग के लिए न्यूनतम लागत खोजने का कार्यक्रम

मान लीजिए कि आकार m की एक सरणी है, एक छोटे से शहर में m घरों का प्रतिनिधित्व करता है, प्रत्येक घर को n रंगों में से एक के साथ चित्रित किया जाना चाहिए (रंगों को 1 से n तक लेबल किया गया है), और कुछ घर पहले से ही चित्रित हैं, इसलिए कोई आवश्यकता नहीं है फिर से पेंट करें। वे घर जो एक ही रंग से रंगे होते हैं पड़ोस कहलाते हैं। हमारे पास सरणी घर हैं, जहां घर [i] घर के रंग का प्रतिनिधित्व करते हैं, यदि रंग मान 0 है, तो यह दर्शाता है कि घर अभी तक रंगीन नहीं है। हमारे पास लागत नामक एक और सरणी है, यह एक 2D सरणी है जहां लागत [i, j] रंग j+1 के साथ घर i को रंगने की लागत का प्रतिनिधित्व करती है। हमारे पास लक्ष्य नामक एक और इनपुट मान भी है। हमें शेष सभी घरों को इस तरह से पेंट करने के लिए आवश्यक न्यूनतम लागत का पता लगाना होगा कि पड़ोस की लक्षित संख्या ठीक हो। अगर हमें समाधान नहीं मिलता है तो -1 लौटें।

तो, अगर इनपुट घरों की तरह है =[0,2,1,2,0] लागत =[[1,10], [10,1], [10,1], [1,10], [5, 1]] n =2 लक्ष्य =3, तो आउटपुट 11 होगा क्योंकि कुछ घर पहले से ही रंगे हुए हैं, इसलिए हमें घरों को इस तरह से रंगना होगा जैसे [2,2,1,2,2], तीन हैं पड़ोस, [{2,2}, {1}, {2,2}]। और पहले और आखिरी घर को पेंट करने की कुल लागत (10 + 1) =11.

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

मी :=घरों का आकार
एक फ़ंक्शन हेल्पर() को परिभाषित करें। इसमें i, p_col, grp
. लगेगा
अगर मैं एम के समान हूं, तो
- वापसी 0 अगर जीआरपी लक्ष्य के समान है अन्यथा inf
अगर मकान [i] 0 के समान नहीं है, तो
- वापसी सहायक (i + 1, घर [i], जीआरपी + (1 अगर p_col घरों के समान नहीं है [i], अन्यथा 0)
कुल :=inf
1 से n तक के कॉलम के लिए, करें
- कुल =कुल का न्यूनतम और (लागत [i, col - 1] + सहायक (i + 1, col, grp + (1 जब p_col col अन्यथा 0) के समान नहीं है))
कुल वापसी
मुख्य विधि से निम्न कार्य करें
उत्तर:=सहायक (0, -1, 0)
अगर उत्तर नहीं है तो वापसी करें अन्यथा -1

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें

def solve(houses, cost, n, target):
   m = len(houses)

   def helper(i, p_col, grp):
      if i == m:

         return 0 if grp == target else float('inf')

      if houses[i] != 0:
         return helper(i + 1, houses[i], grp + int(p_col != houses[i]))

      total = float('inf')
      for col in range(1, n + 1):
         total = min(total, cost[i][col - 1] + helper(i + 1, col, grp + int(p_col != col)))

      return total

   ans = helper(0, -1, 0)
   return ans if ans != float('inf') else -1

houses = [0,2,1,2,0]

cost = [[1,10],[10,1],[10,1],[1,10],[5,1]]

n = 2

target = 3

print(solve(houses, cost, n, target))

इनपुट

[0,2,1,2,0], [[1,10],[10,1],[10,1],[1,10],[5,1]], 2, 3