Giả sử chúng ta có một giá trị n và một mảng được gọi là các vết cắt. Coi có một thanh gỗ dài n đơn vị. Thanh được đánh dấu từ 0 đến n. Ở đây các vết cắt [i] đại diện cho một vị trí mà chúng ta có thể cắt. Chúng ta nên thực hiện các lần cắt theo thứ tự, nhưng chúng ta có thể thay đổi thứ tự của các vết cắt theo ý muốn. Ở đây chi phí của một lần cắt là kích thước của thanh cần cắt và tổng chi phí là tổng chi phí của tất cả các lần cắt. Chúng tôi phải tìm tổng chi phí tối thiểu của việc cắt giảm.
Vì vậy, nếu đầu vào là n =7, cắt =[5,1,4,3], thì đầu ra sẽ là 16 vì nếu chúng ta sắp xếp chúng như [3,5,1,4], thì lúc đầu cắt ở 3 từ chiều dài là 7, do đó chi phí là 7, sau đó chúng tôi có hai phần có chiều dài 3 và 4, sau đó cắt đi 5, do đó chi phí là 4, đến bây giờ tổng số là 7 + 4 =11, sau đó cắt đi 4 từ kích thước thanh 2 , vì vậy tổng chi phí 7 + 4 + 2 =13, sau đó cuối cùng cắt giảm ở mức 3 nên chi phí là 3 và chi phí cuối cùng 7 + 4 + 2 + 3 =16.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
cut:=một danh sách trong đó các phần tử trong các vết cắt được sắp xếp theo thứ tự, và chèn số 0 ở đầu và n ở cuối
-
m:=kích thước vết cắt
-
cost:=tạo một ma trận vuông kích thước m x m và điền bằng 0
-
đối với k trong phạm vi 2 đến m - 1, thực hiện
-
đối với tôi trong phạm vi từ 0 đến m - 1, hãy thực hiện
-
j:=i + k
-
nếu j> =m, thì
-
chuyển sang lần lặp tiếp theo
-
-
chi phí [i, j] =(cắt giảm [j] - cắt giảm [i]) + tối thiểu (chi phí [i, s] + chi phí [s, j] cho tất cả các s trong phạm vi (i + 1, j-1))
-
-
chi phí trả lại [0, m-1]
-
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn
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))
Đầu vào
7, [5,1,4,3]
Đầu ra
16