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
quy hoạch động”, sáng kiến này sẽ giúp học sinh của trường THPT Chuyên Hùng
Vương vận dụng các kiến thức vào làm tốt các dạng đề thi Quốc gia có liên quan về
luồng cực đại, phục vụ cho việc bồi dưỡng học sinh giỏi của trường.
II. Mục đích của đề tài
- Giới thiệu phương pháp giải các bài toán - tin bằng quy hoạch động (QHĐ)
- Các bước giải bài toán - tin bằng phương pháp QHĐ
- Giải một số bài toán bằng phương pháp quy hoạch động điển hình
- Một số bài tập áp dụng có hướng dẫn giải thuật cho học sinh tự làm.
- Từ đó giúp học sinh của trường THPT Chuyên Hùng Vương vận dụng các
kiến thức vào làm tốt các dạng đề thi Quốc gia có dạng quy hoạch động.
Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai
1
Phương pháp giải các bài toán - tin bằng quy hoạch động
III. Nhiệm vụ của nghiên cứu
- Giới thiệu phương pháp giải các bài toán - tin bằng quy hoạch động (QHĐ)
- Các bước giải bài toán - tin bằng phương pháp QHĐ
- Hướng dẫn giải một số bài toán bằng phương pháp quy hoạch động điển hình
- Một số bài tập áp dụng có hướng dẫn giải thuật cho học sinh tự làm.
- Đưa ra một số bài tượng tự để các em học sinh giỏi vận dụng thực hành trên
máy.
IV. Đối tượng nghiên cứu
- Học sinh giỏi tin học 11, 12 của trường THPT Chuyên Hùng Vương.
V. Phương pháp nghiên cứu
- Kết hợp thực tiễn giáo dục ở trường THPT Chuyên Hùng Vương và xu thế ra
đề thi học sinh giỏi Quốc gia của Bộ giáo dục và đào tạo.
- 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 hàng loạt bài toán thông dụng phương pháp này vẫn là một trong các phương
pháp tốt.
1. Phương pháp giải các bài toán - tin bằng quy hoạch động (QHĐ)
Trong nhiều trường hợp, để giải một bài toán đã cho ta đưa về giải một số bài toán
con rồi kết hợp nghiệm của các bài toán con để nhận được nghiệm của bài toán cần
giải. Để giải được các bài toán con này ta lại đưa về giải các bài toán con nhỏ hơn.
Quá trình trên sẽ tiếp tục cho tới khi nhận được các bài toán con có thể giải được dễ
dàng, đó là kỹ thuật chia - để - trị, nó giải các bài toán con nhận được trong quá trình
chia nhỏ một cách độc lập. Phương pháp quy hoạch động cũng có những điểm giống
kỹ thuật chia để trị nhưng trong quá trình phân chia bài toán thành các bài toán con,
các kết quả của mỗi bài toán con được lưu lại để xây dựng kết quả bài toán ban đầu
và tránh giải nhiều lần cùng một bài toán con. Do đó phương pháp quy hoạch động
thường giải bằng kỹ thuật dưới lên (bottom-up).
Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai
3
Phương pháp giải các bài toán - tin bằng quy hoạch động
Ví dụ 1. Tính Cnk (với 0 <=k<=n).
Dễ dàng tính Cnk dựa vào công thức truy hồi Cnk = Cn-1k + Cn-1k-1, với Cji = 1 nếu i=0
hoặc i=j. Hàm tính số tổ hợp chập k của n phần tử được viết theo kỹ thuật chia để trị
như sau :
Function ToHop(k, n : Integer) : Integer;
Begin
If (k=0) or (k=n) then ToHop:=1
Else ToHop:=ToHop(k,n-1)+ToHop(k-1,n-1);
End;
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<=j<=n
C[i,i]=1 với mọi 0<=i<=k
C[i,j]=C[i,j-1]+C[i-1,j-1]
Dựa vào những nhận xét trên ta dễ dàng tính mảng C bằng đoạn chương trình sau:
For j:=0 to n do C[0,j]:=1;
For i:=1 to k do
Begin
C[i,i]:=1;
For j:=i+1 to n do
C[i,j]:=C[i,j-1]+C[i-1,j-1]
End;
2. Các bước giải bài toán - tin bằng phương pháp QHĐ
Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai
4
Phương pháp giải các bài toán - tin bằng quy hoạch động
Quy hoạch động là một phương pháp dựa vào kỹ thuật từ dưới lên. Để giải bài
toán, chúng ta thường xuất phát từ những trường hợp riêng đơn giản nhất của bài
toán (thường là thấy ngay nghiệm của chúng). Nghiệm của bài toán trong những
trường hợp cụ thể được lưu lại rồi kết hợp theo từng bước để nhận được nghiệm của
bài toán có cỡ “lớn hơn” và cuối cùng là nhận được nghiệm của bài toán đã cho. Do
đó khi giải một bài toán con ta chỉ cần tìm những nghiệm của các bài toán con có cỡ
nhỏ hơn mà kết quả đã được giải và lưu trong bảng kết quả mà không cần giải lại.
Chính điều này làm cho các thuật toán quy hoạch động có hiệu quả cao.
Để giải một bài toán bằng phương pháp QHĐ chúng ta phải tiến hành các bước
cơ bản sau:
Tìm nghiệm các bài toán con (các trường hợp riêng) của bài toán.
Tìm công thức (hoặc quy tắc) xây dựng nghiệm của các bài toán con thông
qua nghiệm của các bài toán con cỡ nhỏ hơn (gọi là công thức truy hồi).
Tổ chức cấu trúc dữ liệu hợp lý (thường là dạng bảng) để lưu giữ nghiệm
của các bài toán con. Sau đó tính nghiệm của các bài toán con theo công
thức đã xây dựng ở bước trước và tiếp tục lưu vào bảng.
Từ bảng các nghiệm của các bà toán con đã được làm đầy, tìm cách xây
dựng lời giải cho bài toán.
Các bước trên được liệt kê theo thứ tự nhưng để hình thành các bước này cho
một bài toán cụ thể ta phải tổng hợp tất cả các bước, trong đó nhiệm vụ xây dựng
công thức truy hồi xác định nghiệm (hoặc một thành phần của nghiệm) mới hình
thành được cách giải chính xác. Để minh họa, ta xét một số ví dụ sau :
Ví dụ 2. Dãy con tăng dài nhất
Cho N là một số nguyên dương (0= 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
9
10
11
12
A[i]
6
12
8
11
3
4
1
7
5
9
10
2
1
1
3
0
5
0
6
6
8
10
7
2
2
3
1
2
1
3
3
4
5
2
Truoc[i 0
]
F[i]
1
Để lấy tìm được dãy con không giảm cực đại (yêu cầu của bài toán) ta dùng
một mảng Truoc[1..N] với ý nghĩa Truoc[i] là chỉ số của phần tử trước phần tử i
trong dãy con cực đại lấy trong dãy a1,a2,... ai.
Bây giờ chúng ta phải tìm vị trí i sao cho F[i] đạt max. Ta lưu vị trí đó vào biến Luu.
Như vậy: F[Luu] chính là số lượng phần tử của dãy con cực đại của dãy đã cho. Và
bằng mảng Truoc ta có thể lấy lại chỉ số các phần tử thuộc dãy con đó.
Đế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 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ò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);
Daycon.inp
Daycon.out
15
7
1-->5-->5-->6-->7-->10-->11
2 1 5 5 6 7 13 10 11 4 6 9 8 10 7
Ta có toàn văn chương trình:
uses crt;
type mang=array[1..100]of integer;
var f :text;
a,b,c,truoc : mang;
n,cs: integer;
Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai
7
Phương pháp giải các bài toán - tin bằng quy hoạch động
procedure nhap;
var i:byte;
begin
assign(f,'daycon.inp');
reset(f);
readln(f, n);
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;
(* In ket qua bang de quy *)
procedure xuat(i:integer);
begin
if truoc[i]=0 then
write(f,a[i])
else
begin
xuat(truoc[i]);
write(f,'-->',a[i]);
end;
end;
procedure truyvet;
var max,i : byte;
begin
max:= b[1];cs:=1;
for i:= 2 to n do
if max < b[i] then
begin
max:= b[i];
cs:=i;
end;
assign(f,'daycon.out');
rewrite(f);
writeln(f,max);
Xuat(cs);
Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai
9
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.
Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai
10
Phương pháp giải các bài toán - tin bằng quy hoạch động
Dưới đây là các ví dụ minh họa.
Ví dụ 3: Bài toán Ba lô 1
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<= i <=n. Tìm cách xếp đồ vật vào ba lô sao cho đạt giá trị lớn
nhất.
balo1.inp
4 13
2 4
5 7
3 5
4 6
balo1.out
25
1 1 3 0
B1. Lập hệ thức:
Gọi f(k,v) là giá trị lớn nhất của ba lô đựng trọng lượng v và chỉ chứa các đồ vật
từ 1 đến k.
Nếu k=1 thì f(k,v)=(v div a[1])*c[1]. Giả sử tính được f(s,t) với 1 k vat *)
if (F[i,j]< F[i-1,j-a[i]*k]+C[i]*k) then
(* Neu chon vat i vat so luong k ma gia tri lon hon chap nhan gia tri moi *)
Begin
F[i,j]:=F[i-1,j-a[i]*k]+C[i]*k; (* ghi nhan gia trij F[i,j] *)
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 <- n-1 <- .. <- 1 khong dep lam *)
While (i>0) do
begin
if i>1 then
write(f1,luu[i,w],'<--')
else
write(f1,luu[i,w]);
w:=w-a[i]*luu[i,w];
i:=i-1;
end;
close(f1); }
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 i<>n then
write(f1,luu[i,j],'-->')
else
write(f1,luu[i,j]);
end;
end;
procedure In_ra;
begin
Assign(f1,'balo_1.out');
rewrite(f1);
Writeln(f1,F[n,w]);
Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai
14
Phương pháp giải các bài toán - tin bằng quy hoạch động
find_path(n,w);
close(f1);
end;
begin
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<= i <=n. Tìm cách xếp đồ vật vào ba
lô sao cho đạt giá trị lớn nhất. (số lượng 1 vật có thể chọn 1 hoặc không chọn)
balo2.inp
nw
a[1] c[1]
a[2] c[2]
...
a[n] c[n]
balo2.out
S: Giá trị lớn nhất của các vật đó chọn
num[1] num[2] ... num[n] : số lượng các vật được chọn
Ví dụ:
balo2.inp
4 11
34
56
65
13
Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai
15
Phương pháp giải các bài toán - tin bằng quy hoạch động
balo2.out
13
1101
B1. Lập hệ thức:
Gọi F(i,j) là giá trị lớn nhất của ba lô đựng trọng lượng j và chỉ chứa các đồ vật
từ 1 đến i.
Đặt: F[i,j]=max(F[i-1,j], F[i-1,j-a[i]]+C[i]) (*) ,với i=1,2,...,n, j=1=1,2..,w
B2. Tổ chức dữ liệu và chương trình: Giá trị lớn nhất là F(n,w). Ta dùng mảng
bản ghi a[1..n,1..w] chứa kết quả trung gian. Mỗi bản ghi luu[i,j] chứa giá trị F(i,j)
và giá trị x thoả mãn công thức (*).
B3. Truy vết:
Để 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 luu[n-1,w-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_2;
const MaxN=50;
MaxW=255;
var F,luu:array[0..MaxN,0..MaxW] of Word;
A,C:array[1..MaxN] of 0..255;
n,W:integer;f1:text;
procedure input;
var
i,j:integer;
begin
assign(f1,'Balo_2.inp');
Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai
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
else
begin
F[i,j]:=f[i-1,j];luu[i,j]:=0; (* ghi nhan vat i khong chon *)
Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai
17
Phương pháp giải các bài toán - tin bằng quy hoạch động
end;
end;
end;
(***************************)
{ procedure In_ra; (* nguoc thu tu n0) do
begin
write(f1,luu[i,w],' ');
w:=w-a[i]*luu[i,w];
i:=i-1;
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 i<>n 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);
close(f1);
end;
begin
input;
Qh_dong;
In_ra;
end.
3) BÀI TẬP ÁP DỤNG
Bài 1. Đổi tiền
Có n loại tiền có trị giá A1, A2, ..., An. Hãy dùng các loại tiền này đổi số tiền L sao
cho tổng số tờ tiền là ít nhất.
Hướng dẫn :
Công thức truy toán:
Gọi F(L) là số tờ tiền ít nhất cần dùng để đổi được số tiền L.
Ta có nhận xét :
Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai
19
- Xem thêm -