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

สมมติว่ามีอาร์เรย์ของขนาด m หมายถึง m บ้านในเมืองเล็ก ๆ บ้านแต่ละหลังจะต้องทาสีด้วยสี n สีใดสีหนึ่ง (สีมีป้ายกำกับตั้งแต่ 1 ถึง n) และบ้านบางหลังทาสีแล้วจึงไม่จำเป็นต้องทาสี ทาสีอีกครั้ง บ้านเหล่านั้นที่มีสีเดียวกันเรียกว่าเพื่อนบ้าน เรามีบ้านอาร์เรย์ โดยที่ houses[i] แทนสีของบ้าน ถ้าค่าสีเป็น 0 แสดงว่าบ้านยังไม่มีสี เรามีอาร์เรย์อื่นที่เรียกว่า cost ซึ่งเป็นอาร์เรย์ 2 มิติที่ cost[i, j] แทนต้นทุนของ color house i ด้วยสี j+1 นอกจากนี้เรายังมีค่าอินพุตอื่นที่เรียกว่าเป้าหมาย เราต้องหาต้นทุนขั้นต่ำที่จำเป็นในการทาสีบ้านที่เหลือทั้งหมด เพื่อให้มีจำนวนย่านใกล้เคียงเป้าหมายที่แน่นอน หากเราไม่สามารถแก้ปัญหาได้ ให้คืนค่า -1

ดังนั้น ถ้า input เหมือนกับ house =[0,2,1,2,0] cost =[[1,10],[10,1],[10,1],[1,10],[5, 1 ] n =2 เป้าหมาย =3 ผลลัพธ์จะเป็น 11 เพราะบ้านบางหลังทาสีแล้วเราจึงต้องทาสีบ้านในลักษณะเช่น [2,2,1,2,2] มีสาม ย่าน, [{2,2}, {1}, {2,2}]. และค่าใช้จ่ายทั้งหมดในการทาสีบ้านหลังแรกและบ้านหลังสุดท้าย (10+1) =11

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

• ม :=ขนาดบ้าน

• กำหนดฟังก์ชั่น helper() นี่จะใช้เวลา i, p_col, grp

• ถ้าฉันเหมือนกับ m แล้ว

  • คืนค่า 0 ถ้า grp เหมือนกับเป้าหมาย มิฉะนั้น inf

• ถ้า house[i] ไม่เหมือนกับ 0 แล้ว

  • ตัวช่วยส่งคืน (i + 1, houses[i], grp + (1 ถ้า p_col ไม่เหมือนกับ houses[i] มิฉะนั้น 0)

• รวม :=inf

• สำหรับ col ในช่วง 1 ถึง n ทำ

  • รวม =ต่ำสุดของยอดรวมและ (ค่าใช้จ่าย[i, col - 1] + helper(i + 1, col, grp + (1 เมื่อ p_col ไม่เหมือนกับ col ไม่เช่นนั้น 0)))

• ผลตอบแทนรวม

• จากวิธีหลักให้ทำดังนี้

• ตอบ :=ผู้ช่วย(0, -1, 0)

• ส่งคืน ans ถ้า ans ไม่ได้ inf เป็นอย่างอื่น -1

ตัวอย่าง

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

def Solver(บ้าน, ราคา, n, เป้าหมาย):m =len(houses) def helper(i, p_col, grp):if i ==m:return 0 if grp ==target else float('inf' ) ถ้า houses[i] !=0:return help(i + 1, houses[i], grp + int(p_col !=houses[i])) total =float('inf') สำหรับ col in range(1, n + 1):total =min(total, cost[i][col - 1] + helper(i + 1, col, grp + int(p_col !=col))) คืนค่าทั้งหมด ans =helper(0, -1 , 0) return ans if ans !=float('inf') else -1houses =[0,2,1,2,0]ราคา =[[1,10],[10,1],[10,1] ,[1,10],[5,1]]n =2target =3print(แก้ปัญหา(บ้าน, ต้นทุน, n, เป้าหมาย))

อินพุต

ผลลัพธ์

11