ต้นทุนขั้นต่ำในการตัดกระดานเป็นสี่เหลี่ยมใน Python

สมมติว่าเรามีกระดานยาว p และกว้าง q; เราต้องแบ่งบอร์ดนี้ออกเป็นจำนวน p*q ของช่องสี่เหลี่ยมเพื่อให้ค่าใช้จ่ายในการทำลายน้อยที่สุดเท่าที่จะเป็นไปได้ ค่าตัดสำหรับแต่ละขอบจะได้รับ

ดังนั้น หากอินพุตเป็นเหมือน X_slice =[3,2,4,2,5], Y_slice =[5,2,3]

แล้วผลลัพธ์จะเป็น 65

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

• res :=0
• แนวนอน :=1 แนวตั้ง :=1
• i :=0, j :=0
• ในขณะที่ฉัน
• ถ้า X_slice[i]> Y_slice[j] แล้ว
  • res :=res + X_slice[i] * แนวตั้ง
  • แนวนอน :=แนวนอน + 1
  • ผม :=ผม + 1
• มิฉะนั้น
  • res :=res + Y_slice[j] * แนวนอน
  • แนวตั้ง :=แนวตั้ง + 1
  • j :=j + 1

ตัวอย่าง

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

def minCost(X_slice, Y_slice, m, n):
   res = 0
   X_slice.sort(reverse = True)
   Y_slice.sort(reverse = True)
   horizontal = 1
   vertical = 1
   i = 0
   j = 0
   while i < m and j < n:
      if (X_slice[i] > Y_slice[j]):
         res += X_slice[i] * vertical
         horizontal += 1
         i += 1
      else:
         res += Y_slice[j] * horizontal
         vertical += 1
         j += 1
   total = 0
   while (i < m):
      total += X_slice[i]
      i += 1
   res += total * vertical
   total = 0
   while (j < n):
      total += Y_slice[j]
      j += 1
   res += total * horizontal
   return res
m = 6; n = 4
X_slice = [3,2,4,2,5]
Y_slice = [5,2,3]
print(minCost(X_slice, Y_slice, m-1, n-1))

อินพุต

[3,2,4,2,5],[5,2,3]

ผลลัพธ์

65