Tổ chức dữ liệu cho các bài toán quy hoạch động
Nguyễn Xuân Huy
Số trước ta đã bàn về việc tiết kiệm biến và tăng tốc cho các thủ tục quy hoạch động. Số
này sẽ minh họa thêm một số bài toán từ các kỳ thi học sinh giỏi địa phương và quốc tế.
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 hoạ.
Bài toán 1. (Cắm hoa, đề thi Olimpic Quốc tế năm 1999)
Cần cắm k bó hoa khác loại nhau vào n lọ xếp thẳng hàng sao cho hoa có số hiệu nhỏ
được đặt trước hoa có số hiệu lớn. Với mỗi loại hoa i ta biết giá trị thẩm mỹ khi cắm hoa
đó vào lọ j, v[i,j]. Các số liệu đều là số tự nhiên và được ghi cách nhau bởi dấu cách trên
mỗi dòng.
Dữ liệu vào ghi trong tệp văn bản HOA.INP: dòng đầu tiên là hai trị k và n. Từ dòng thứ
hai trở đi là các giá trị v[i,j] với i:=1..k và j:=1..n; 1 ≤ k ≤ n ≤ 100.
Dữ liệu ra ghi trong tệp văn bản HOA.OUT gồm hai dòng: dòng đầu tiên là tổng giá trị
thẩm mỹ của phương án cắm hoa tối ưu. Từ dòng thứ hai là dãy k số hiệu lọ được chọn
cho mỗi bó hoa.
Thí dụ:
Bài giải:
Trước hết ta đọc dữ liệu từ tệp HOA.INP vào các biến k, n và v[i,j].
Procedure doc;
var i,j:byte;
Begin
assign(f,fn); reset(f);

Tổng hợp lại ta có giá trị tối ưu khi cắm i bó hoa vào j lọ sẽ là:
T(i,j)=max {T(i-1,j-1)+v[i,j], T(i,j-1)}.
2. Tổ chức dữ liệu và chương trình: Nếu dùng mảng 2 chiều T thì ta có thể tính như trong
bảng dưới đây:
Ngoài ra ta còn cần đặt trong mỗi ô của bảng trên một mảng dữ liệu bao gồm n phần tử để
đánh dấu lọ hoa nào được chọn cho mỗi tình huống. Gọi mảng dữ liệu đó là L[i,j], ta dễ
thấy là nên điền bảng lần lượt theo từng cột, tại mỗi cột ta điền bảng từ trên xuống hoặc
dưới lên theo luật sau:
Nếu T[i-1,j-1]+v[i,j] > T[i,j-1] thì ta phải thực hiện 2 thao tác:
+Đặt lại trị T[i,j]:= T[i-1,j-1]+v[i,j], và
+Ghi nhận việc chọn lọ hoa j trong phương án mới, cụ thể lấy phương án cắm hoa (i-1,j-1)
rồi bổ sung thêm việc chọn lọ hoa j như sau:
- Đặt L[i,j]:=L[i-1,j-1] và đánh dấu phần tử j trong mảng L[i,j].
-Nếu T[i-1,j-1]+v[i,j] ≤ T[i,j-1] thì ta chỉ cần copy L[i,j-1] sang L[i,j], vì ta bảo lưu phương
án (i,j-1).
3. Làm tốt: Phương án dùng mảng hai chiều tốn kém về miền nhớ. Ta có thể dùng một
mảng một chiều T[0..100] xem như một cột của bảng T nói trên. Ta duyệt j bước, tại bước
thứ j, giá trị T[i] sẽ là trị tối ưu khi cắm i bó hoa vào j lọ. Như vậy, tại bước thứ j ta có:
- Nếu T[i-1] cũ + v[i,j] > T[i] cũ thì ta phải thực hiện 2 thao tác:
+Đặt lại trị T[i]:= T[i-1] cũ + v[i,j], và
+Ghi nhận việc chọn lọ hoa j trong phương án mới, cụ thể lấy phương án cắm hoa (i-1) ở
bước j-1 rồi bổ sung thêm việc chọn lọ hoa j như sau:
- Đặt L[i]:=L[i-1] cũ và đánh dấu phần tử j trong mảng L[i].
-Nếu T[i-1] cũ + v[i,j] ≤ T[i] cũ thì ta không phải làm gì vì sẽ bảo lưu phương án cũ.
Biểu thức so sánh cho biết khi cập nhật mảng T từ bước thứ j-1 qua bước thứ j ta phải tính
từ dưới lên, nghĩa là tính dần theo chiều giảm của i := j..1.
Để đánh dấu các lọ hoa ta dùng mảng L[0..MN] mỗi phần tử là một dãy 15 byte. Nếu dùng
một bit cho mỗi lọ hoa thì với 15 byte ta có thể đánh dấu cho 15*8=120 lọ hoa. Khi cần
đánh dấu lọ hoa thứ j trong dãy L[i] ta bật bít thứ j. Khi cần xem lọ thứ j có được chọn hay
không ta gọi hàm GetBit.