สมมติว่าเรามีค่า 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 จนถึงตอนนี้รวมเป็น 7+4=11 แล้วตัดที่ 4 จากขนาดแท่งที่ 2 ดังนั้นค่าใช้จ่ายทั้งหมด 7+4+2 =13 จากนั้นจึงตัดที่ 3 ดังนั้นค่าใช้จ่ายจึงเป็น 3 และต้นทุนสุดท้าย 7+4+2+3 =16
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ตัด :=รายการที่องค์ประกอบในการตัดอยู่ในลำดับที่เรียงลำดับ และแทรก 0 ที่จุดเริ่มต้นและ n ที่ส่วนท้าย
-
m :=ขนาดตัด
-
ราคา :=สร้างเมทริกซ์สี่เหลี่ยมจัตุรัสขนาด m x m และเติมด้วย 0
-
สำหรับ k ในช่วง 2 ถึง m - 1 ทำ
-
สำหรับฉันในช่วง 0 ถึง m - 1 ทำ
-
เจ :=ผม + k
-
ถ้า j>=m แล้ว
-
ไปทำซ้ำต่อไป
-
-
cost[i, j] =(cuts[j] - cuts[i]) + ขั้นต่ำของ (ราคา[i, s] + cost[s, j] สำหรับ s ทั้งหมดในช่วง (i+1, j-1))
-
-
ค่าส่งคืน[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
