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ụnggiả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ạycho ra kết quả đúng trong thời gian ngắn cho phép. Tuy nhiên, không phải bàitoá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ũngcó không ít bài toán đúng là có thể giải bằng quy hoạch động nhưng việc pháthiệ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ìnhgiả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ụngtrong 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,Ylà hai số nguyên dương. Kí hiệu Sx là tổng các chữ số trong dạngbiể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ánhạ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 chotrướ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ớiX 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 filevă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àinà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ảicho 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
