Một số bài toán quy hoạch động

Đỗ Quang Tiến




Khi gặp một bài toán tin có yêu cầu tìm kết quả tối ưu về một hay nhiều tính chất nào đấy, hẳn không ít người nghĩ ngay đến sử dụng giải thuật quy hoạch động để giải bài toán. Tại sao lại vậy? Bởi vì quy hoạch động thường có độ phức tạp tính toán không cao nghĩa là chương trình sẽ chạy cho ra kết quả đúng trong thời gian ngắn cho phép. Tuy nhiên, không phải bài toán với yêu cầu tối ưu nào cũng có thể giải bằng quy hoạch động, mặt khác cũng có không ít bài toán đúng là có thể giải bằng quy hoạch động nhưng việc phát hiện và áp dụng phương pháp này để giải là không đơn giản.
Việc phát hiện cũng như áp dụng quy hoạch động để giải bài toán phụ thuộc rất lớn vào khả năng tư duy của bạn và đặc biệt là những kinh nghiệm mà bạn có.
Bài viết này sẽ không đề cập đến những khái niệm cơ bản của quy hoạch động vì những khái niệm này đã quá quen thuộc với mọi người. Bài viết chỉ dừng ở mức phân tích cụ thể lời giải của một số bài toán khá hay, từ đó hy vọng ít nhiều giúp bạn có thêm một chút kinh nghiệm trong lập trình giải quyết các bài toán tin.
Trước tiên ta cùng xét một bài toán đã được sử dụng trong kỳ thi Olympic Tin học sinh viên Thủ đô năm 1998.
Bài 1. Giá trị biểu thức
Giả thiết X,Y là hai số nguyên dương. Kí hiệu Sx là tổng các chữ số trong dạng biểu diễn cơ số 10 của X, Dmax_y là chữ số lớn nhất và Dmin_y là chữ số nhỏ nhất trong dạng biểu diễn cơ số 10 của Y. Phép tính hai ngôi # với các toán hạng nguyên dương X,Y được định nghĩa như sau:
( X#Y ) = Sx*Dmax_y + Dmin_y
Ví dụ:
(30#9) = 3*9 + 9 = 36
(9#30) = 9*3 + 0 = 27
Với X cho trước, một số biểu thức hợp lệ là:
(X#X)
((X#X)#X)
(X#(X#X)#(X#X)#X)
Ký hiệu kết quả biểu thức là K. Cho X và K (0 < X,K < 109-1) cần xác định số ít nhất m các phép # để từ đó có thể xây dựng biểu thức thuộc dạng đang xét với X cho kết quả K và biểu diễn của biểu thức.
Dữ liệu vào từ file văn bản BT.IN, dòng thứ nhất chứa X, dòng thứ hai chứa K.
Kết quả ra file văn bản BT.OUT, dòng thứ nhất chứa m, dòng thứ hai chứa biểu thức.
Ví dụ:
BT.IN
BT.OUT

718
81
3
((718 #(718 #718)) #718)

Thực ra đề bài này cũng dễ hiểu không phức tạp lắm, bây giờ ta đi vào phân tích tìm lời giải cho bài toán. Trước tiên nhận xét rằng cho 0 < X, K < 109 nên:
1 =< Sx =< 9*9
1 =< Dmax_x =< 9
0 =< Dmin_x =< 9
từ đó 1 =< X#X =< 9*9*9+9 = 738, tức là biểu thức có một dấu # luôn mang giá trị tròng đoạn [1,738]. Suy rộng hơn thì giá trị của một biểu thức hợp lệ bất kỳ phải nằm trong đoạn [1,738], đây chính là cốt lõi lời giải cho bài toán.
Rõ ràng ta chỉ chấp nhận các giá trị K thoả mãn 1 =< K =< 738, nếu K nằm ngoài khoảng này thì chắc chắn vô nghiệm.
Xét biểu thức X#X có 1 dấu #, dễ thấy có 3 cách mở rộng biểu thức 1 dấu # này là:
-  X#(X#X)
-  (X#X)#X
-  (X#X)#(X#X)
Giả sử B là một biểu thức tạo bởi X và n dấu # thế thì có 3 cách mở rộng biểu thức này là:
-  X#B  (n+1 dấu #)
-  B#X  (n+1 dấu #)
-  B#B  (2*n+1 dấu #)
Ta lập mảng một chiều L[1..738] trong đó L[i] cho biết số phép # ít nhất để từ X tạo ra kết quả là i, i=1..738. Dễ thấy mảng L mang tính truy hồi, lần ngược và khi làm cụ thể ta thực hiện như sau:
1.  Khởi tạo mảng A[1..738] := 0, mảng A đánh dấu các giá trị đã tạo được từ biểu thức có X và #; khởi tạo mảng L nhận các giá trị Maxint.
2.  Tìm T