Dynamic programming - rod cutting (Quy hoạch động)

Dynamic programming - rod cutting (Quy hoạch động)
Hãy xem bài toán đơn giản sau:
Có một thanh thép dài n = 10 mét
Có thể bán thanh thép với độ dài và giá tương ứng theo bảng sau:

Độ dài	1	2	3	4	5	6	7	8	9	10
Giá	1	5	8	9	10	17	17	20	24	30

Thanh độ dài 1: giá 1$

Thanh độ dài 2: giá 5$

....

Thanh độ dài 10: giá 30$

Câu hỏi đặt ra là: chúng ta nên cắt thanh thép như thế nào để có được số tiền lớn nhất?

Chúng ta có thể dễ dàng giải quyết bài toán với độ dài n=1,2,3 

R1 = 1

R2 = 5

R3 = 8

Với n=4 chúng ta có 8 cách cắt như sau: 

4 thanh độ dài = 1, R4=4

1 Thanh độ dài =1, 1 Thanh độ dài = 2, 1 thanh độ dài 1, R4=7

2 thanh độ dài = 2, R4 = 10

....

Như vậy R4=10 (cắt thành 2 thanh độ dài 2)

Số phương án cắt sẽ tăng theo hàm số mũ: 2 mũ (n-1) (với n là độ dài của thanh thép)

(*) Một cách tổng quát thì chúng ta sẽ thấy: Rn = Max(Pn, R1 + Rn-1, R2+ Rn-2, ... Ri + Rn-i .. ,Rn-1 + R1)

Với n=10, P10 = 30 như trên bảng giá ở trên, bài toán của chúng ta bây giờ là tìm i, để Ri + Rn-i là lớn nhất trong đó i = 1...n.

Có thể xem đoạn code đơn giản được viết bằng c# ở đây

Nếu chúng ta tăng n bằng cách thêm vào mảng prices, có thể dễ dàng thấy thời gian thực hiện sẽ tăng theo. (2 mũ n-1)

Quay lại (*) chúng ta nhận thấy để tìm Rn chúng ta có thể đưa về bài toàn tìm Ri và Rn-i; và rõ ràng i và n-i là các bài toán nhỏ hơn.

(**) Rn-1 = Max(Pn-1, R1 + Rn-2, ..., Rn-2 + R1)

Chúng ta để ý sẽ thấy 2 dãy (*) và (**) sẽ chỉ khác nhau R1 + Rn-1 => như vậy nếu chúng ta lưu lại kết quả tính toán ở các bước thì ở những phép tính với bài toán lớn hơn phía sau sẽ tiết kiệm được rất nhiều bước tính toán

Các bạn có thể thử với đoạn code được bổ sung phần cache lưu lại kết quả tính toán ở đây

Trên đây là một ví dụ các các bài toán được gọi là Dynamic Programming, các bạn có thể tìm kiếm chi tiết hơn.

Câu hỏi:

Các bạn hãy tìm các bài toán tương tự có thể áp dụng cách tiếp cận này không?