Chương trình tìm chi phí tối thiểu để sơn hàng rào với k màu khác nhau bằng Python

Giả sử chúng ta muốn sơn một dãy N hàng rào với K màu khác nhau. Chúng tôi muốn giảm thiểu chi phí trong khi đảm bảo rằng không có hai hàng rào lân cận có cùng màu. Vì vậy, nếu chúng ta có ma trận N x K trong đó hàng thứ n và cột thứ k biểu thị chi phí để sơn hàng rào thứ n với màu thứ k, chúng ta phải tìm chi phí tối thiểu để đạt được mục tiêu này.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 14, vì chúng ta có thể chọn các chỉ số màu sau (bắt đầu từ hàng rào đầu tiên) - 5 → 2 → 3 → 4.

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

• n:=số hàng của ma trận

• fc:=0, ft:=0

• sc:=1, st:=0

• đối với mỗi hàng trong ma trận, thực hiện

  • nfc:=-1, nft:=inf

  • nsc:=-1, nst:=inf

  • đối với mỗi chỉ số i và hàng giá trị t, thực hiện

    • ct:=t + (ft nếu tôi không giống với fc nếu không thì st)

    • nếu ct <=nft, thì

      • nsc:=nfc, nst:=nft

      • nfc:=i, nft:=ct

    • ngược lại khi ct <=nst, thì

      • nsc:=i, nst:=ct

  • fc:=nfc, ft:=nft

  • sc:=nsc, st:=nst

• trở lại ft

Ví dụ

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

class Solution:
   def solve(self, matrix):
      n = len(matrix)
      fc, ft = 0, 0
      sc, st = 1, 0
      inf = int(1e18)
      for row in matrix:
         nfc, nft = -1, inf
         nsc, nst = -1, inf
         for i, t in enumerate(row):
            ct = t + (ft if i != fc else st)
            if ct <= nft:
               nsc, nst = nfc, nft
               nfc, nft = i, ct
            elif ct <= nst:
               nsc, nst = i, ct
         fc, ft = nfc, nft
         sc, st = nsc, nst
      return ft

ob = Solution()
matrix = [
   [6, 4, 5],
   [3, 2, 7],
   [3, 4, 5],
   [5, 4, 4]
]
print(ob.solve(matrix))

Đầu vào

[
   [6, 4, 5],
   [3, 2, 7],
   [3, 4, 5],
   [5, 4, 4]
]

Đầu ra

14