home

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

โปรแกรมหาค่าใช้จ่ายขั้นต่ำในการตัดไม้ใน Python

สมมติว่าเรามีค่า n และอาร์เรย์ชื่อ cuts พิจารณาว่ามีไม้ยาว n หน่วย ไม้ติดป้าย 0 ถึง n cuts[i] แทนตำแหน่งที่เราสามารถตัดได้ เราควรตัดตามลำดับ แต่สามารถเปลี่ยนลำดับการตัดได้ ค่าใช้จ่ายของการตัดหนึ่งครั้งคือขนาดของไม้ที่จะตัด และค่าใช้จ่ายรวมคือผลรวมของค่าใช้จ่ายทั้งหมด เราต้องหาค่าใช้จ่ายรวมขั้นต่ำของการตัด

เช่น ถ้าอินพุตคือ n = 7, cuts = [5,1,4,3] ผลลัพธ์จะเป็น 16 เพราะถ้าจัดลำดับเป็น [3,5,1,4] ตัดที่ 3 จากความยาว 7 ค่าใช้จ่าย 7 เหลือสองส่วนยาว 3 และ 4 ตัดที่ 5 ค่าใช้จ่าย 4 รวม 11 ตัดที่ 4 จากไม้ยาว 2 รวม 13 ตัดที่ 3 ค่าใช้จ่าย 3 รวม 16

โปรแกรมหาค่าใช้จ่ายขั้นต่ำในการตัดไม้ใน Python

วิธีแก้ปัญหา

  • cuts := รายการที่เรียง cuts แล้ว เพิ่ม 0 ตัวหน้า และ n ตัวท้าย
  • m := ขนาดของ cuts
  • cost := สร้างเมทริกซ์สี่เหลี่ยมขนาด m x m เติม 0
  • สำหรับ k ในช่วง 2 ถึง m - 1:
    • สำหรับ i ในช่วง 0 ถึง m - 1:
      • j := i + k
      • ถ้า j >= m: ข้ามรอบถัดไป
      • cost[i, j] = (cuts[j] - cuts[i]) + min(cost[i, s] + cost[s, j] สำหรับ s ทุกตัวในช่วง i+1 ถึง j-1)
  • return cost[0, m-1]

ตัวอย่าง

def solve(n, cuts):
    cuts = [0] + sorted(cuts) + [n]
    m = len(cuts)
    cost = [[0]*m for _ in range(m)]
    for k in range(2, m):
        for i in range(m):
            j = i + k
            if j >= m:
                continue
            cost[i][j] = (cuts[j]-cuts[i]) + min(cost[i][s] + cost[s][j] for s in range(i+1, j))
    return cost[0][m-1]

n = 7
cuts = [5,1,4,3]
print(solve(n, cuts))

อินพุต

7, [5,1,4,3]

เอาต์พุต

16