Thuật toán Quan hệ động và tổ chức dữ liệu

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ụ: