Qui hoạch động với các bài toán có dữ liệu lớn
Cao Minh Anh
Như chúng ta đã biết khi giải một bài toán thì vấn đễ thời gian và dữ liệu là cốt lõi. Vì thế
trong các kì thi chúng ta thường gặp các bài có dữ liệu lớn. Những bài nay thường rất khó
bởi vì ta vừa phải giải quyết vấn đề dữ liệu, vừa phải giải quyết vấn đề thời gian. Vì thế
khi có được một thuật toán hay tối ưu vẫn chưa chắc giải được những bài này, tối ưu chưa
đủ mà cần phải có phương pháp cài đặt tốt để có thể giải quyết về mặt dữ liệu. Quy hoạch
động tượng trưng cho sự tối ưu hoá về thời gian vì thế tôi xin trình bày một số bài toán dữ
liệu lớn dùng quy hoạch động đễ giải và cách thức xử lý của từng bài toán.
Bài 1: Tìm số lớn nhất.
Cho n số nguyên (n<=2
32
) trong file max.inp, hãy tìm số lớn nhất trong n số nguyên đã
cho. Kết quả được viết vào file max.out gồm 2 số M, P − trong đó M là số lớn nhất và P là
vị trí của nó trong n số nguyên. Nếu có nhiều kết quả đưa ra số lớn nhất có vị trí lớn nhất.
Ví dụ:
Đây là một bài quy hoạch động rất đơn giản, tôi muốn đề cập để các bạn thấy rằng bài toán
tìm max là một bài toán rất cơ bản, ai học cũng biết bài toán này nhưng chắc các bạn sẽ
không nghĩ rằng đây là một bài toán qui hoạch động đơn giản mà ai cũng có thể làm được.
Tôi muốn giới thiệu với các bạn bài toán tìm max với dữ liệu lớn dùng file để chứa các
phần tử thay vì dùng mảng, như thế ta vừa tiết kiệm được dữ liệu vừa giải quyết bài toán
nhanh nhất.
uses crt;
const
fi=’max.inp’;
go=’max.out’;
var max,n,k :longint;
f,g :text;
procedure Openf;
begin
assign(f,fi);

end.
Bài 2: Cho N số tự nhiên nằm trong khoảng [0..9], hãy tìm dãy tăng dài nhất dài nhất.
Dữ liệu vào: File daytang.inp gồm dòng đầu tiên là số N.N dòng tiếp theo là N số tự
nhiên.
Dữ liệu ra: File daytang.out gồm 2 số M là chiều dài của dãy tăng dài nhất.
Ví dụ:
- Nếu bài trên với dữ liệu N khoảng 10000 thì ta có thể giải quyết theo cách sau:
+ Nhập N số trên vào mảng a.
+ Gọi Fx[i] là chiều dài dài nhất của dãy tăng kết thúc là phần tử a[i].
Như vậy ta có chương trình quy hoạch đơn giản như sau:
procedure Quyhoach;
var i,j:integer;
begin
for i:=1 to n do fx[i]:=1;
for i:=2 to n do
for j:=i-1 downto 1 do
if a[j]<=a[i] then
if fx[i]
Muốn xuất kết quả ta chỉ cần writeln(Max(fx[1],fx[2],..,fx[n]));
Nhưng nếu bài toán trên với dữ liệu lớn không thể bỏ vào mảng thì ta không thể giải quyết
theo phương pháp trên được.
Ta chú ý các số chỉ nằm trong khoảng [0..9] vì thế thay vì dùng mảng Fx[i] là chiều dài dãy
tăng lớn nhất khi a[i] cuối dãy ta có thể dùng mảng Fx[i] là chiều dài dãy tăng lớn nhất khi
i đứng cuối dãy. Như thế chỉ cần khai báo:
Var fx : array[0..9] of longint;
Như vậy khi nhập một số k. Thì số k có thể đặt sau dãy tăng có tận cùng là 0,1,2..k. Như
vậy thì fx[k] sẽ bằng
Fx[k]:=max(Fx[0]+1,Fx[1]+1,Fx[2]+1,..,fx[k]+1)
Với cách làm như thế thì bài toán trở nên đơn giản hơn rất nhiều vài có thể giải quyết với
N rất lớn.

end;
procedure Findmax;
var i:integer;
begin
max:=0;
for i:=0 to 9 do
if fx[i]>max then max:=fx[i];
end;
procedure Xuat;
var i:integer;
begin
writeln(g,max);
end;
begin
clrscr;
openf;
Quyhoach;
Findmax;
Xuat;
Closef;
end.
Chúng ta có thể dùng với các số tự nhiên lớn hơn không nhất thiết là từ [0..9] chỉ cần khai
báo mảng Fx lớn hơn là được.Sau đây chúng ta chuyển qua một bài toán dùng qui hoạch
động rất hay đó là bài Cấp số cộng.
Bài 3: Cấp số cộng (Đề thi quốc gia bảng Bm).
Cho một tệp văn bản gồm N (N rất lớn) số nguyên a1, a2, a3,..,an với Abs(ai)<=30 000.
Hãy tìm trong dãy A đó một dãy con dài nhất lập thành một dãy cấp số cộng có công sai là
d. Với 0<D<=100.
Dữ liều vào: Csc. INP
- Dòng đầu ghi số N