Tiết kiệm biến cho bài toán quy hoạch động

Tiết kiệm biến cho các bài toán quy hoạch động

Nguyễn Xuân Huy




Các bài toán quy hoạch động (QHĐ) chiếm một vị trí khá quan trọng trong việc tổ chức hoạt động và sản xuất. 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. Thông thường những bạn nào dùng phương pháp quay lui, vét cạn cho các bài toán QHĐ thì chỉ có thể vét được các tập dữ liệu nhỏ, kích thước chừng vài chục byte. Nếu tìm được đúng hệ thức thể hiện bản chất QHĐ của bài toán và khéo tổ chức dữ liệu thì ta có thể xử lý được những tập dữ liệu khá lớn.
Có thể tóm lược nguyên lý QHĐ do Bellman phát biểu như sau: Quy hoạch động là lớp các bài toán mà quyết định ở bước thứ i phụ thuộc vào quyết định ở các bước đã xử lý trước đó.
Để giải các bài toán QHĐ ta có thể theo sơ đồ sau đây:
Sơ đồ giải bài toán QHĐ:
1.  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ễ gây ra hiện tượng tràn miền nhớ khi ta tổ chức chương trình trực tiếp bằng đệ quy.
2.  Tổ chức dữ liệu và chương trình: Tổ chức dữ 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 chúng ta hay gặp đòi hỏi một vài mảng hai chiều.
3.  Làm tốt: Làm tốt thuật toán bằng cách thu gọn hệ thức QHĐ và giảm kích thước miền nhớ.
Dưới đây là thí dụ minh họa.
Bài toán 1: (Chia thưởng) Cần chía hết m phần thưởng cho n học sinh sắp theo thứ tự từ giỏi trở xuống sao cho mỗi bạn không nhận ít phần thưởng hơn bạn xếp sau mình.
Bài giải:
1. Lập hệ thức: Gọi Chiăm,n) là số cách chia m phần thưởng cho n học sinh, ta thấy:
1.1. Nếu không có học sinh nào (n=0) thì không có cách chia nào (Chia=0).
1.2. Nếu không có phần thưởng nào (m=0) thì chỉ có một cách chia (Chia =1 - mỗi học sinh nhận 0 phần thưởng). Ta cũng quy ước Chiă0,0)=1.
1.3. Nếu số phần  thưởng ít hơn số học sinh (m< m
1.4. Ta xét trường hợp m>=n. Ta tách các phương án chia thành hai nhóm không giao nhau:
-  Nhóm thứ nhất gồm các phương án trong đó học sinh thứ n không được nhận thưởng, tức là m phần thưởng chỉ chia cho n-1 học sinh và do đó số cách chia, tức là số phần tử của nhóm này sẽ là: Chiăm,n-1).
- Nhóm thứ hai gồm các phương án mà học sinh thứ n cũng được nhận thưởng. Khi đó, do học sinh đứng cuối bảng thành tích được nhận thưởng thì mọi học sinh khác cũng sẽ có thưởng. Do ai cũng được thưởng nên ta bớt của mỗi người một phần thưởng (để họ lĩnh sau), số phần thưởng còn lại (m-n) sẽ được chia cho n học sinh. Số cách chia khi đó sẽ là Chiăm-n,n).
Tổng số cách chia cho trường hợp m>=n sẽ là tổng số phần tử của hai nhóm, ta có: Chiăm,n)=Chiăm,n-1)+Chiăm-n,n).
2. Tổ chức dữ liệu và chương trình: Ta có phương án đầu tiên của giải thuật Chia như sau:
{PHUONG AN 1: de quy}
function Chiam,n: integer):longint;
begin
 if m = 0 then Chia:=1
else {m>0}
if n = 0 then {m>0;n=0} Chia:=0
else {m,n > 0}
if m < n then {0
else {m>=n>0}
Chia:=Chiam-n,n)+Chiam,n-1);
end; 
Làm tốt lần 1: Phương án 1 khá dễ triển khai nhưng chương trình sẽ  chạy rất lâu, bạn hãy thử gọi Chiă66,32) để cảm nhận được điều trên. Diễn tả đệ quy thường trong sáng, nhàn tản, nhưng khi thực hiện sẽ sinh ra hiện tượng gọi lặp lại những hàm đệ quy. Cải tiến đầu tiên là tránh những lần gọi lặp như vậy. Muốn thế chúng ta tính sẵn các giá trị của hàm theo các trị của đầu vào khác nhau và điền vào một mảng hai chiều cc. Mảng cc được mô tả như sau:
const MN=100;{gioi han tren cua m va n}
var cc:array[0..MN,