โปรแกรมหาต้นทุนขั้นต่ำในการทาบ้านใน Python

ปัญหา

มี m บ้าน ต้องทาสี n สี (1..n) บางหลังทาแล้ว (0 = ยังไม่ทา) บ้านที่ติดกันและสีเหมือนกันเรียกว่า "neighborhood" มี cost[i][j] = ต้นทุนทาบ้าน i สี j+1 หาต้นทุนน้อยที่สุดเพื่อให้มี neighborhood ทั้งหมด 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] มี 3 neighborhoods: {2,2},{1},{2,2} ต้นทุน 10+1=11)

ขั้นตอนการแก้ปัญหา

1. m := len(houses)
2. ฟังก์ชัน helper(i, p_col, grp):
   • ถ้า i == m: คืน 0 ถ้า grp == target มิฉะนั้น inf
   • ถ้า houses[i] != 0: คืน helper(i+1, houses[i], grp + (p_col != houses[i]))
   • total := inf
   • วน col 1 ถึง n:
     • total = min(total, cost[i][col-1] + helper(i+1, col, grp + (p_col != col)))
   • คืน total
3. ans := helper(0, -1, 0), คืน ans ถ้าไม่ใช่ inf มิฉะนั้น -1

การนำไปใช้งาน (Python)

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