Chương trình tìm chi phí sơn nhà tối thiểu bằng Python

Giả sử có một mảng kích thước m, đại diện cho m ngôi nhà trong một thành phố nhỏ, mỗi ngôi nhà phải được sơn một trong n màu (các màu được đánh dấu từ 1 đến n), Và một số ngôi nhà đã được sơn rồi nên không cần sơn lại. Những ngôi nhà có màu giống nhau được gọi là khu phố. Chúng ta có các ngôi nhà mảng, trong đó các ngôi nhà [i] đại diện cho màu của ngôi nhà, nếu giá trị màu là 0, thì nó đại diện cho ngôi nhà chưa được tô màu. Chúng ta có một mảng khác được gọi là chi phí, đây là mảng 2D trong đó chi phí [i, j] thể hiện chi phí để tô màu ngôi nhà i với màu j + 1. Chúng tôi cũng có một giá trị đầu vào khác được gọi là target. Chúng ta phải tìm ra chi phí tối thiểu cần thiết để sơn tất cả các ngôi nhà còn lại sao cho có chính xác số lượng khu vực lân cận mục tiêu. Nếu chúng tôi không thể tìm được giải pháp thì hãy trả về -1.

Vì vậy, nếu đầu vào giống như nhà =[0,2,1,2,0] chi phí =[[1,10], [10,1], [10,1], [1,10], [5, 1]] n =2 target =3, thì đầu ra sẽ là 11 vì một số ngôi nhà đã được sơn, vì vậy chúng ta phải sơn các ngôi nhà theo cách như [2,2,1,2,2], Có ba vùng lân cận, [{2,2}, {1}, {2,2}]. Và tổng chi phí sơn căn nhà đầu tiên và căn nhà cuối cùng (10 + 1) =11.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

m:=kích thước của ngôi nhà
Định nghĩa một hàm trợ giúp (). Điều này sẽ mất i, p_col, grp
nếu tôi giống với m, thì
- trả về 0 nếu grp giống với target, ngược lại là inf
nếu các nhà [i] không giống 0 thì
- trả về trình trợ giúp (i + 1, nhà [i], grp + (1 nếu p_col không giống nhà [i], nếu không thì 0)
tổng:=inf
đối với col trong phạm vi từ 1 đến n, thực hiện
- tổng =tối thiểu của tổng và (cost [i, col - 1] + helper (i + 1, col, grp + (1 khi p_col không giống col khác 0)))
tổng trả lại
Từ phương thức chính, hãy làm như sau
ans:=helper (0, -1, 0)
trả về ans nếu ans không phải là khác -1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn

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))

Đầu vào

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

Chương trình tìm chi phí sơn nhà tối thiểu bằng Python

Ví dụ

Đầu vào

Đầu ra