home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

โปรแกรมหาต้นทุนขั้นต่ำในการทาสีรั้วด้วย k สีต่างๆ ใน ​​Python

สมมติว่าเราต้องการทาสีแถว N รั้วด้วยสี K ที่ต่างกัน เราต้องการลดต้นทุนในขณะที่ทำให้แน่ใจว่าไม่มีรั้วสองรั้วที่อยู่ใกล้เคียงที่มีสีเดียวกัน ดังนั้น หากเรามีเมทริกซ์ N x K โดยที่แถวที่ n และคอลัมน์ที่ k แทนต้นทุนในการทาสีรั้วที่ n ด้วยสีที่ k เราต้องหาต้นทุนขั้นต่ำที่จะบรรลุเป้าหมายนี้

ดังนั้นหากอินพุตเป็นแบบ

6 4 5
3 2 7
3 4 5
5 4 4

จากนั้นผลลัพธ์จะเป็น 14 เนื่องจากเราสามารถเลือกดัชนีสีต่อไปนี้ (เริ่มจากรั้วแรก) − 5 → 2 → 3 → 4

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

  • n :=จำนวนแถวของเมทริกซ์

  • fc :=0, ft :=0

  • sc :=1, st :=0

  • สำหรับแต่ละแถวในเมทริกซ์ ทำ

    • nfc :=-1, nft :=inf

    • nsc :=-1, nst :=inf

    • สำหรับแต่ละดัชนี i และค่า t แถว ทำ

      • ct :=t +(ft if i ไม่เหมือนกับ fc มิฉะนั้น st)

      • ถ้า ct <=nft แล้ว

        • nsc :=nfc, nst :=nft

        • nfc :=i, nft :=ct

      • มิฉะนั้นเมื่อ ct <=nst แล้ว

        • nsc :=i, nst :=ct

    • fc :=nfc, ft :=nft

    • sc :=nsc, st :=nst

  • กลับฟุต

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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

อินพุต

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

ผลลัพธ์

14