Bài6.pascal

Chơng I: Quy Hoạch Động

Các Bài toán quy hoạch động chiếm một vị trí khá quan trọng trong việc tổ chức hoạt động và sản xuất ( Nhất là việc giải quyết các bài toán tối u ). Chính vì lẽ đó mà trong các kỳ thi học sinh giỏi Quốc Gia và Quốc Tế chúng ta thờng gặp loại toán này . T tởng chủ đạo của phơng pháp này dựa trên nguyên lí tối u của BellMan phát biểu nh sau :
"Nếu một dãy các lựa chọn là tối u thì mọi dãy con của nó cũng tối u "
Ngoài ra khi thiết kế các thuật toán quy hoạch động ta thờng dùng kỹ thuật "Phân vùng để xử lí " , Nghĩa là để giải quyết một bài toán lớn ta chia nó thành nhiều bài toán con có thể giải quyết độc lập . Trong phơng pháp quy hoạch động ,việc thể hiện nguyên lí này đợc đẩy đến cực độ . Để giải quyết các bài toán quy hoạch động ta có thể theo sơ đồ sau :
a.) Lập hệ thức : Lập hệ thức biểu diễn tơng quan quyết định của bớc đang xử lí với các bớc đã xử lí trớc đó. Hệ thức này thờng là các biểu thức đệ quy do đó dễ thấy hiện tợng tràn bộ nhớ
b.) Tổ chức dữ liệu chơng trình : Tổ chức giữ liệu tính toán dần theo từng bớc .Nên tìm cách khử đệ quy .Thông thờng ,trong các bài toán tin chúng ta hay gặp đòi hỏi một vài mảng lớn .
c.) Làm tốt : Làm tốt thuật toán bằng cách thu gọn hệ thức quy hoạch động và giảm kích thớc miền nhớ .
Các thao tác tổng quát của quy hoạch động :
1. Xây dựng hàm quy hoạch động
2. Lập bảng lu lại giá trị của hàm
3. Tính các giá trị ban đầu của bảng
4. Tính các giá trị còn lại theo kích thớc tăng dần của bảng cho đến khi đạt đợc giá trị tối u cần tìm
5. Dùng bảng lu để truy xuất lời giải tối u.
Trong các lời hớng dẫn các bài toán , chúng tôi sẽ đa các bạn đi theo từng phần nh sơ đồ giải quyết trên . Chúng ta có thể phân loại các bài toán quy hoạch động theo nhiều cách . Để các bạn tiện theo dõi , tôi xin phân loại theo cách lu( tức là tổ chức chơng trình )là các mảng một chiều hay nhiều chiều .
I. Dạng Một:
Đa Phần dạng bài toán thờng gặp trong loại này đó là loại có công thức truy hồi nh sau :
Mind[I]:=Min Mind[J] +Giá Trị Để tồn tại JI ;J=0..I Hoặc là :
Maxd[I]:=MaxMaxd[J]+Giá Trị Để tồn tại JI ;J=0..I .
Chúng ta có thể thấy rõ ràng đối với các bài toán mà chúng ta sẽ xét sau đây :
Bài Toán 1: Bài Đổi Tiền
Đề Bài :
"Cho một ngân hàng có N loại tiền mệnh giá A[1],A[2],...A[N] với số lợng tiền mỗi loại không giới hạn . Cần chi trả cho khách hàng một số tiền M đồng . Hãy cho biết cần bao nhiêu tiền mỗi loại để chi trả sao cho số lợng tờ là ít nhất .
Dữ liệu vào từ File : Tien.Inp Nh sau :
Dòng đầu tiên ghi 2 số N,M . ( N<=100,M<=10000)
Dòng thứ hai ghi N Số : A[1], A