SỞ GIÁO DỤC VÀ ĐÀO TẠO GIA LAI
TRƯỜNG THPT CHUYÊN HÙNG VƯƠNG
TỔ TOÁN TIN

ĐỀ TÀI:

“PHƯƠNG PHÁP GIẢI BÀI TOÁN TIN BẰNG
QUY HOẠCH ĐỘNG”

Người thực hiện: LÊ VĂN TRƯỜNG
Giáo viên: Tin học

Pleiku, 2/2014


Phương pháp giải các bài toán - tin bằng quy hoạch động

PHƯƠNG PHÁP GIẢI BÀI TOÁN TIN BẰNG QUY HOẠCH ĐỘNG
A. PHẦN MỞ ĐẦU
I. Lí do chọn đề tài
Hiện nay tài liệu dạng chuyên đề nâng cao phục vụ cho việc bồi dưỡng học sinh
giỏi môn Tin học là chưa thật sự đầy đủ và tổng quát, đặc biệt là những chuyên đề
khá mới và rất khó của thế giới, giờ đã được đưa vào các đề thi học sinh giỏi Quốc
gia như: Quy hoạch động, Luồng cực đại trên mạng,…
Từ thực tiễn giảng dạy tin tại trường THPT Chuyên Hùng Vương tôi thấy rằng
để đạt hiệu quả cao trong bồi dưỡng học sinh giỏi, cần có cách thiết kế bài giảng cho
phù hợp với nội dung kiến thức dựa trên tài liệu chuyên đề đầy đủ rõ ràng từ lý
thuyết đến bài tập và theo đúng xu thế chung của các kì thi học sinh giỏi các cấp
hiện nay và trong tương lai, điều kiện tiến quyết để mang lại thành tích cao cho đội
tuyển học sinh giỏi trong các kì thi.
Xuất phát từ cơ sở trên, tôi đã chọn đề tài “Phương pháp giải bài toán tin bằng

- Có tham khảo các tài liệu bồi dưỡng học sinh giỏi trong và ngoài nước.
- Tham khảo một số dạng đề thi học sinh giỏi Quốc gia của Bộ giáo dục và đào
tạo dạng quy hoạch một số năm gần đây.
B. NỘI DUNG
I. Cơ sở lí luận
- Các cách tiếp cận về tri thức mới, hiện đại của học sinh trong trường THPT
Chuyên Hùng Vương là rất khó khăn vì thiếu tài liệu chuyên sâu về bồi dưỡng học
sinh giỏi tin học tiếng Việt, nếu có thì cũng chưa thật đầy đủ, tổng quát, còn tài liệu
tiếng Anh thì nhiều mà khả năng đọc hiểu của các em thì chưa thật sự tốt.

Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai

2


Phương pháp giải các bài toán - tin bằng quy hoạch động

- Vì vậy tôi đã tham khảo tài liệu trong và ngoài nước để viết lên sáng đề tài về
phương pháp quy hoạch động từ lý thuyết đến thuật toán và có một số bài toán cho
các em vận dụng để thực hành trên máy tính. Từ đó các em có thể làm tốt các đề bài
có dạng tương tự trong các kì thi chọn học sinh giỏi tin học.
II. Nội dung và giải pháp thực hiện
II.1 Nội Dung
I. MỞ ĐẦU
Tư tưởng quy hạch động được Bellman đề cập từ 1960 nhằm tìm nghiệm của
bài toán tối ưu. Thời kỳ 1960-1970 là thời kỳ phát triển rực rỡ nhất của phương pháp
này, nhờ nó nhiều bài toán với kích thước dữ liệu lớn hơn đã được giải với tốc độ
chạy chương trình nhanh hơn so với những cách giải trước đây. Song đến năm 1970
đã xuất hiện một số bài toán mới mà cách giải bằng quy hoạch động tỏ ra hạn chế,
chỉ tương đối có hiệu quả, thậm chí có bài hầu như không có hiệu qủa. Tuy nhiên

Với cách viết như trên thì có nhiều giá trị của tổ hợp được tính lại nhiều lần,
chẳng hạn để tính ToHop(3,5) ta phải tính 2 lần ToHop(2,3); 3 lần ToHop(1,2),... Do
đó thời gian tính toán sẽ rất lớn khi các giá trị đầu vào lớn.
Để khắc phục hạn chế trên, ta dùng một mảng C[0..k,0..n] để lưu các kết quả đã
tính, với mỗi i,j ta chỉ cần tính một lần Cji và lưu vào C[i,j]. Mảng C được xây dựng
theo nguyên tắc từ dưới lên với những nhận xét sau:
C[0,j]=1 với mọi 0
Ý tưởng của thuật toán quy hoạch động ở đây là: Để xây dựng dãy con không giảm
dài nhất của dãy đã cho chúng ta sẽ xây dựng dãy con không giảm dài nhất của đoạn
i phần tử đầu a1, a2,... ai.
Để làm được điều đó: ta gọi F[i] là số lượng phần tử nhiều nhất của dãy con không
giảm, trong đó ai cũng thuộc dãy con trên (nó là phần tử cuối cùng).
Chúng ta sẽ tính F[i] ở từng bước dựa vào các giá trị tính được của các bước trước
được lưu ở F[i-1],... F[1] như sau:
+ Ban đầu F[i] với i = 1, 2,... N được gán bằng 1 vì trường hợp xấu nhất thì
dãy con chỉ là một phần tử.
+ Với mỗi i >= 2 thì F[i] được tính bằng công thức truy hồi sau:
F[i]=Max{F[j]+1} với j=i-1,... 1 mà aj < ai.
Ví dụ :
i

1

2

3

4

5

6

7

8


10

2

1

1

3

0

5

0

6

6

8

10

7

2

2



Đến đây ta gặp một vấn đề: Mảng Truoc chỉ cho phép ta lần ngược từ cuối về đầu dó
đó để in ra các chỉ số theo thứ tự tăng dần ta phải dùng thêm một mảng phụ P và in
ngược lại của mảng P:

Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai

6


Phương pháp giải các bài toán - tin bằng quy hoạch động

dem:=0;
i:=Luu;
While i0 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òng lệ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);

for i:=1 to n do
read(f,a[i]);
close(f);
end;

procedure taobang;
var i,j,bMax,chiso : byte;
begin
b[1]:=1; truoc[1]:=0;
for i:= 2 to n do
begin
bmax:= 0; chiso:=0;
for j:= i-1 downto 1 do
if (a[j] <= a[i]) and (b[j] > bmax) then
begin
bmax:= b[j];
chiso:= j;
end;
b[i] := bmax +1;
truoc[i] := chiso;
end;

Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai

8


Phương pháp giải các bài toán - tin bằng quy hoạch động

end;



Phương pháp giải các bài toán - tin bằng quy hoạch động

(*while truoc[cs]0 do
begin
write(a[cs]:3);
write(F,a[cs]:3);
cs:=truoc[cs];
end;
write(a[cs]:3);
write(F,a[cs]:3); *)

close(f);
end;
begin
nhap;
taobang;
truyvet;
end.
3) Sơ đồ giải bài toán QHĐ:
B1. 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.
B2. 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.
B3. Truy vết: tìm kết quả của bài toán tử bảng một chiều hoặc hai chiều đã xây
dựng.

bản ghi a[1..n,1..w] chứa kết quả trung gian. Mỗi bản ghi a[k,v] chứa giá trị f(k,v) và
giá trị x thoả mãn công thức (*).
B3. Truy vết:

Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai

11


Phương pháp giải các bài toán - tin bằng quy hoạch động

Để xác định số lượng x[i] đồ vật i thoả mãn điều kiện tối ưu, ta xuất phát từ
a[n,w] xác định được x[n]. Nhảy tới a[n-1,w-x[n]*a[n]] xác định được x[n-1]. Cứ
như vậy tới x[1].
Sau đây là lời giải, chương trình được viết bằng ngôn ngữ Pascal:
Toàn bộ chương trình:
program Ba_lo_1;
uses crt;
const MaxN=50;
MaxW=255;
var F,luu:array[0..MaxN,0..MaxW] of Word;
A,c,num:array[1..MaxN] of 0..255;
n,W:integer;f1:text;
procedure input;
var
i,j,k:integer;
begin
assign(f1,'Balo_1.inp');
reset(f1);
readln(f1,n,W);

luu[i,j]:=k; (* Ghi nhan vat i da chon voi so luong la k *)
End;
end;
end;
(***************************)
{ procedure In_ra;
Var i:integer;
begin
Assign(f1,'balo_1.out');
rewrite(f1);
Writeln(f1,F[n,w]);
i:=n;
(* viet ra so luong cac vat theo thu tu nguoc

Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai

13


Phương pháp giải các bài toán - tin bằng quy hoạch động

n
input;
Qh_dong;
In_ra;
end.
Ví dụ 4: Bài toán ba lô 2: Cho ba lô chứa được trọng lượng tối đa là w. Có n đồ vật,
đồ vật thứ i có khối lượng a[i] và giá trị c[i], 1

16


Phương pháp giải các bài toán - tin bằng quy hoạch động

reset(f1);
readln(f1,n,W);
For i:=1 to n do
readln(f1,a[i],c[i]);
close(f1);
end;
procedure QH_dong;
Var i,j:integer;
begin
For j:=1 to W do
Begin
F[0,j]:=0;
Luu[0,j]:=0;
end;
For i:=1 to n do (* duyet het cac vat tu 1 den n *)
For j:=1 to W do (* duyet het kich co tui tu 1 den w *)
Begin
if j>=a[i] then (* neu co tui lon hon vat i *)
if (F[i-1,j]< F[i-1,j-a[i]]+C[i]) then
(* neu chon vat i co gia tri lon hon khong chon no thi chap nhan *)
Begin
F[i,j]:=F[i-1,j-a[i]]+C[i]; (*ghi nhan gia tri F[i,j] *)
luu[i,j]:=1; (* ghi nhan vat i co chon *)
End

close(f1);
end;

}

procedure Find_path(i,j:integer); (* In bang de quy dung thu tu *)
begin
if (i>0) then
begin
find_path(i-1,j-a[i]*luu[i,j]);
if in then

Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai

18


Phương pháp giải các bài toán - tin bằng quy hoạch động

write(f1,luu[i,j],'-->')
else
write(f1,luu[i,j]);
end;
end;
procedure In_ra;
begin
Assign(f1,'balo_2.out');
rewrite(f1);
Writeln(f1,F[n,w]);
find_path(n,w);

Bài 2. Cho một hình tam giác các con số như hình vẽ. Từ một con số bất kỳ, ta chỉ
có thể đi xuống qua con số bên trái hoặc bên phải ở hàng dưới. Xuất phát từ đỉnh
hình tam giác và đi xuống cho đến đáy hình tam giác. Hãy tìm đường đi sao cho
tổng các con số có được trên đường đi là nhỏ nhất/lớn nhất.
2
5

4

1

7

3

10

5

8

1

1

0

4

7

biến đổi nhất và thông báo tiếp vào file OUT.TXT theo quy cách như trên.
Hướng dẫn :
Giả sử độ dài của S1, S2 tương ứng là M và N. Ta xây dựng mảng A[0..M,0..N] mà
A[i,j] bằng số phép biến đổi ít nhất cần dùng để biến đổi đoạn đầu độ dài i của S1
thành đoạn đầu độ dài j của S2. Ta có A[0,j] = j và A[i,0]=i với 0
1

4

8

1

5

16

1

6

32

1

7

64

1

8

128


21 19

Giả sử có trong tay số ít nhất M đồng tiền để tổng giá trị là V, tổng trọng lượng là
W, và trong M đồng này có một đồng loại i, thế thì với tổng giá trị V - vi, tổng trọng
lượng W - wi chắc chắn cần số ít nhất là M-1 đồng tiền, i = 1..N.
Từ nhận xét trên ta dùng mảng Coin[1..150,1..150], với Coin[i,j] cho biết số tối thiểu
đồng tiền thỏa mãn điều kiện số đồng tiền này có tổng giá trị là i, tổng trọng lượng là
j, (i=1..V, j=1..W), thế thì:
Coin[i,j]=Min{Coin[i-v[k],j-w[k]]+1}, i = 1..V, j=1..W, k = 1..N.
Bài 6. Thuê máy
Tại thời điểm 0, ông chủ 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 n khá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ụng máy từ thời điểm di đến thời điểm ci (di, ci là các số nguyên và 0
< di < ci < 1000000000) và sẽ trả tiền sử dụng máy là pi (pi nguyên, 0
24

1 200 100

200 513 500

400 800 80

100 325 200
600 900 600

Bài toán này chúng ta phải chú ý ở chỗ: Để dùng thuật toán Quy hoạch động tối ưu
từng bước thì trước hết chúng ta phải sắp xếp các ci theo thứ tự tăng dần:
Giả sử c1 =< c2 =