Thuật toán quy hoạch động trên mảng một chiều
Trần Minh Quang
Bài toán 1: Cho một dãysố nguyên dương a
1
, a
2
,... a
N
. Hãy tỉa bớt mộtsố ít nhất các phần tử
của dãy số nguyên đó và giữ nguyên thứ tự các phần tửcòn lại sao cho dãy số còn lại là
một dãy tăng dần. Ta gọi dãy số nguyên tăngdần còn lại sau khi đã tỉa bớt một số phần tử
là dãy con của dãy đã cho.
Input: Dữ liệu vào được cho bởi tệp văn bản với quy cách:
- Dòng đầu ghi số N là sốphần tử
- Dòng tiếp theo ghi N sốlà các số nguyên của dãy.
Output:
-Ghi ra màn hình: Số lượng phần tử của dãy con cực đại và chỉ số các phần tửtrong dãy
con đó (theo thứ tự tăng dần).
Ví dụ:
- Với Input trong fileDAYSO.INP như sau:
10
10 100 20 1 2 50 70 80 3 60
- thì Output phải là:
1 2 50 70 80
ý tưởng của thuật toánquy hoạch động ở đây là: Để xây dựng dãy con dài nhất của dãy đã
cho chúngta sẽ xây dựng dãy con dài nhất của đoạn phần tử đầu a
1
, a
2
,...a
i

While i<>0 do
Begin
Inc(dem);P[dem]:=i;i:=Truoc[i];
End;
Chỉ số theo thứ tự tăng dần của dãy con cực đại được in ra bằng dònglệnh:
For i:=dem downto 1 do Write(P[i],' ');
Tuy nhiên làm như trên có vẻ dài dòng trong khi chúng ta đã nhận ra tínhđệ quy trong việc
lấy ngược lại. Và thủ tục in ra dãy con đã rất ngắn gọn vàsáng sủa:
Procedure Print(i:Integer);
Begin
If i>0 then
Begin
Print(Truoc[i]);Write(i,' ');
End;
End;
Công việc in ra chỉ cần một lời gọi: Print(Luu);
Ta có toàn văn chương trình:
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+,Y+}
{$M 65500,0,655360}
Uses Crt;
Const fi = 'DAYSO.INP';
MaxN=5000;
Var A : Array[1..MaxN] ofInteger;
S :Array[1..MaxN] of Integer;
Truoc : Array[1..MaxN]of Integer;
i,j,Luu : Word;
N : Word;
Procedure Init;
Begin
Fillchar(S,SizeOf(S),1);

End;
Procedure OutputResult;
Begin
Luu:=N;
For i:=N-1 downto 1 do
If S[i]>S[Luu] then Luu:=i;
Print(Luu);
End;
BEGIN
Clrscr;
Init;
Readfile;
Find;
OutputResult;
Readln;
END.
Qua ví dụ trên chúng ta đã hiểu cách mà thuật toán thể hiện. Bây giờchúng ta sẽ xét tiếp
một bài toán sắp xếp trình tự phục vụ khách hàng mà cáchgiải đều sử dụng thuật toán Quy
hoạch động trên mảng một chiều.
Ta xét tiếp mộtví dụ sau:
Bài toán 2: Tại thời điểm 0, ôngchủ một máy tính hiệu năng cao nhận được đơn đặt hàng
thuê sử dụng máy của nkhách hàng. Các khách hàng được đánh số từ 1 đến n. Khách hàng
i cần sử dụngmáy từ thời điểm d
i
đến thời điểm c
i
(d
i
, c
i