Python में घरों को रंगने की न्यूनतम लागत खोजने का प्रोग्राम

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

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

समाधान के चरण

1. m := len(houses)
2. helper() फंक्शन परिभाषित करें जो i, p_col, grp लेता है
3. यदि i == m:
   • 0 वापस करें यदि grp == target अन्यथा inf
4. यदि houses[i] != 0:
   • helper(i + 1, houses[i], grp + int(p_col != houses[i])) वापस करें
5. total := inf
6. col को 1 से n तक:
   • total = min(total, cost[i][col - 1] + helper(i + 1, col, grp + int(p_col != col)))
7. total वापस करें
8. मुख्य मेथड से:
   • ans := helper(0, -1, 0)
   • ans वापस करें यदि ans != inf अन्यथा -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

आउटपुट

11