Sáng kiến kinh nghiệm 2014 – Mai Hồng Kiên -THPT chuyên

SỞ GIÁO DỤC VÀ ĐÀO TẠO LÀO CAI
TRƯỜNG THPT CHUYÊN TỈNH LÀO CAI

----------

SÁNG KIẾN KINH NGHIỆM
ỨNG DỤNG PHƯƠNG PHÁP QHĐ VÀO GIẢI QUYẾT MỘT
SỐ BÀI TOÁN TRONG TIN HỌC

HỌ TÊN GIÁO VIÊN: MAI HỒNG KIÊN
Đơn vị: Tổ Toán - tin

Năm học 2013 – 2014
1


Sáng kiến kinh nghiệm 2014 – Mai Hồng Kiên -THPT chuyên

MỤC LỤC
Nội dung
1 . Đặt vấn đề
2. Giải quyết vấn đề
2.1 Cơ sở lý luận
2.2 Thực trạng vấn đề
2.3 Các biện pháp thực hiện giải quyết vấn đề
2.3.1 Áp dụng phương pháp QHĐ
2.3.2 Ví dụ minh họa
2.3.3 Một số bài toán tối ưu giải bằng phương pháp QHĐ
2.4 Hiệu quả của SKNN

theo.
- Trong chương trình Tin học THPT lớp 10 học sinh được giới thiệu các kiến thức đại
cương về tin học, lớp 11 học sinh được giới thiệu về lập trình, lớp 12 học sinh được học
về cơ sở dữ liệu. Trong chương trình Tin học THPT thì chương trình lớp 11 là phần
được cho là khó nhất, học sinh phải làm quen với ngôn ngữ lập trình Pascal và nắm
được một số thuật toán. Chương trình tin học lớp 11 nhằm rèn luyện tư duy về thuật
toán cho học sinh, rèn luyện kĩ năng lập trình, tính kiên trì, tỉ mỉ cẩn thận.
- Tuy nhiên từ thực tiễn giảng dạy học sinh đại trà cũng như học sinh đội tuyển tin học
của trường THPT chuyên Lào Cai tôi thấy rằng, học sinh gặp khó khăn khi chuyển lời
giải các bài toán từ toán sang ngôn ngữ lập trình. Đặc biệt là việc phân tích bài toán,
nhận biết bài toán đó có thể giải quyết bằng phương pháp nào, cỏ lời giải tối ưu hay
không ?
Xuất phát từ cơ sở trên, tôi đã chọn đề tài “Áp dụng phương pháp quy hoạch động để
giải các bài toán tối ưu trong tin học”, giúp các học sinh nắm được phương pháp quy
hoạch động khi giải quyết những bài toán tối ưu trong tin học.

3


Sáng kiến kinh nghiệm 2014 – Mai Hồng Kiên -THPT chuyên

2. Giải quyết vấn đề
2.1 .Cơ sở lí luận
- Nguyên lý tối ưu của Bellman
Phương pháp quy hoạch động cùng nguyên lý tối ưu được nhà toán học Mỹ
R.Bellman đề xuất vào những năm 50 của thế kỷ 20. Phương pháp này đã được áp dụng
để giải hàng loạt bài toán thực tế trong các quá trình kỹ thuật cộng nghệ, tổ chức sản
xuất, kế hoạch hoá kinh tế…
Trong thực tế, ta thường gặp một số bài toán tối ưu loại sau: Có một đại lượng f
hình thành trong một quá trình gồm nhiều giai đoạn và ta chỉ quan tâm đến kết quả cuối

lượng số hạng của dãy B là nhiều nhất, điều khiển ở giai đoạn i thể hiện việc chọn hay
không chọn Ai vào dãy B.
Giả sử dãy đã cho là 1 8 10 2 4 6 7. Nếu ta chọn lần lượt 1, 8, 10 thì chỉ chọn
được 3 số hạng nhưng nếu bỏ qua 8 và 10 thì ta chọn được 5 số hạng 1, 2, 4, 6, 7.
Khi giải một bài toán bằng cách “chia để trị” chuyển việc giải bài toán kích thước
lớn về việc giải nhiều bài toán cùng kiểu có kích thước nhỏ hơn thì thuật toán này
thường được thể hiện bằng các chương trình con đệ quy. Khi đó, trên thực tế, nhiều kết
quả trung gian phải tính nhiều lần.
Vậy ý tưởng cơ bản của quy hoạch động là : Tránh tính toán lại mọi thứ hai lần,
mà lưu giữ kết quả đã tìm kiếm được vào một bảng làm giả thiết cho việc tìm kiếm
những kết quả của trường hợp sau.
Chúng ta sẽ làm đầy dần giá trị của bảng này bởi các kết quả của những trường
hợp trước đã được giải. Kết quả cuối cùng chính là kết quả của bài toán cần giải. Nói
cách khác phương pháp quy hoạch động đã thể hiện sức mạnh của nguyên lý chia để trị
đến cao độ.
Quy hoạch động là kỹ thuật thiết kế bottom-up (từ dưới lên). Nó được bắt đầu với
những trường hợp con nhỏ nhất (thường là đơn giải nhất và giải được ngay). Bằng
cách tổ hợp các kết quả đã có (không phải tính lại) của các trường hợp con, sẽ đạt đạt
5


Sáng kiến kinh nghiệm 2014 – Mai Hồng Kiên -THPT chuyên

tới kết quả của trường hợp có kích thước lớn dần lên và tổng quát hơn, cho đến khi
cuối cùng đạt tới lời giải của trường hợp tổng quát nhất.
Trong một số trường hợp, khi giải một bài toán A, trước hết ta tìm họ bài toán
A(p) phụ thuộc tham số p (có thể p là một véc tơ) mà A(p0)=A với p0 là trạng thái ban
đầu của bài toán A. Sau đó tìm cách giải họ bài toán A(p) với tham số p bằng cách áp
dụng nguyên lý tối ưu của Bellman. Cuối cùng cho p=p 0 sẽ nhận được kết quả của bài
toán A ban đầu.

Hay là: F1 (t (k )) = m
∀d ( k )

Bước 2: Tổ chức dữ liệu và chương trình
Tổ chức dữ liệu sao cho đạt các yêu cầu sau:


Dữ liệu được tính toán dần theo các bước.



Dữ liệu được lưu trữ để giảm lượng tính toán lặp lại.



Kích thước miền nhớ dành cho lưu trữ dữ liệu càng nhỏ càng tốt, kiểu dữ

liệu được chọn phù hợp, nên chọn đơn giản dễ truy cập.
Cụ thể
• Các giá trị của Fk thường được lưu trữ trong một bảng (mảng một chiều hoặc
hai, ba, v.v… chiều).
• Cần lưu ý khởi trị các giá trị ban đầu của bảng cho thích hợp, đó là các kết
quả của các bài toán con có kích cỡ nhỏ nhất của bài toán đang giải:
F1 (t (1)) = m ax {G 1 (t (1), d (1)) + F0 (t (0))}
∀d (1)

• Dựa vào công thức, phương trình truy toán (*) và các giá trị đã có trong bảng
để tìm dần các giá trị còn lại của bảng.
• Ngoài ra còn cần mảng lưu trữ nghiệm tương ứng với các giá trị tối ưu trong
từng gian đoạn.

Nếu gọi F[m, v] là số cách phân tích số v thành tổng các số nguyên dương ≤ m. Khi
đó: Các cách phân tích số v thành tổng các số nguyên dương ≤ m có thể chia làm hai
loại:
-

Loại 1: Không chứa số m trong phép phân tích, khi đó số cách phân tích loại này
chính là số cách phân tích số v thành tổng các số nguyên dương < m, tức là số cách
phân tích số v thành tổng các số nguyên dương ≤ m - 1 và bằng F[m - 1, v].

-

Loại 2: Có chứa ít nhất một số m trong phép phân tích. Khi đó nếu trong các cách
phân tích loại này ta bỏ đi số m đó thì ta sẽ được các cách phân tích số v - m thành
tổng các số nguyên dương ≤ m (Lưu ý: điều này chỉ đúng khi không tính lặp lại các
8


Sáng kiến kinh nghiệm 2014 – Mai Hồng Kiên -THPT chuyên

hoán vị của một cách). Có nghĩa là về mặt số lượng, số các cách phân tích loại này
bằng F[m, v - m]
Trong trường hợp m > v thì rõ ràng chỉ có các cách phân tích loại 1, còn trong
trường hợp m ≤ v thì sẽ có cả các cách phân tích loại 1 và loại 2. Vì thế:

F[m 1, v]; if m > v
F[m, v]= 
F[m-1,v]+F[m,v-m]; if m ≤ v
Bước 2: Tổ chức dữ liệu và chương trình
Ta có công thức xây dựng F[m, v] từ F[m - 1, v] và F[m, v - m]. Công thức này có
tên gọi là công thức truy hồi đưa việc tính F[m, v] về việc tính các F[m', v'] với dữ liệu

1
2
2
2
2

3
0
1
2
3
3
3

4
0
1
3
4
5
5

5 V
0
1
3
5
6
7


nhận thấy rằng khi đã tính xong dòng thứ k thì việc lưu trữ các dòng từ dòng 0 tới dòng
k - 1 là không cần thiết bởi vì việc tính dòng k + 1 chỉ phụ thuộc các giá trị lưu trữ trên
dòng k. Vậy ta có thể dùng hai mảng một chiều: Mảng Current lưu dòng hiện thời đang
xét của bảng và mảng Next lưu dòng kế tiếp, đầu tiên mảng Current được gán các giá trị
tương ứng trên dòng 0. Sau đó dùng mảng Current tính mảng Next, mảng Next sau khi
tính sẽ mang các giá trị tương ứng trên dòng 1. Rồi lại gán mảng Current := Next và
tiếp tục dùng mảng Current tính mảng Next, mảng Next sẽ gồm các giá trị tương ứng
trên dòng 2 v.v… Vậy ta có cài đặt cải tiến sau:
program Analysis_Counting_2;
const max = 100;
var
Current, Next: array[0..max] of Integer;
n, m, v: Integer;
begin
Write('n = '); ReadLn(n);
FillChar(Current, SizeOf(Current), 0);
Current[0] := 1;
for m := 1 to n do
begin
for v := 0 to n do
if v < m then Next[v] := Current[v]
else Next[v] := Current[v] + Next[v - m];
Current := Next;
end;
WriteLn(Current[n], ' Analyses');
end.
10


Sáng kiến kinh nghiệm 2014 – Mai Hồng Kiên -THPT chuyên

521

44
54
9 10
44

Bài giải:
Nếu gọi F[i, j] là giá trị lớn nhất có thể có bằng cách chọn trong các gói {1, 2, …,
i} với giới hạn trọng lượng j. Thì giá trị lớn nhất khi được chọn trong số n gói với giới
hạn trọng lượng M chính là F[n, M].
Công thức truy hồi tính F[i, j].
11


Sáng kiến kinh nghiệm 2014 – Mai Hồng Kiên -THPT chuyên

Với giới hạn trọng lượng j, việc chọn tối ưu trong số các gói {1, 2, …, i - 1, i} để
có giá trị lớn nhất sẽ có hai khả năng:
o Nếu không chọn gói thứ i thì F[i, j] là giá trị lớn nhất có thể bằng cách chọn trong
số các gói {1, 2, …, i - 1} với giới hạn trọng lượng là j. Tức là F[i, j] = F[i - 1, j]
o Nếu có chọn gói thứ i (tất nhiên chỉ xét tới trường hợp này khi mà W[i] ≤ j) thì
F[i, j] bằng giá trị gói thứ i là V[i] cộng với giá trị lớn nhất có thể có được bằng
cách chọn trong số các gói {1, 2, …, i - 1} với giới hạn trọng lượng j - W[i]. Tức
là về mặt giá trị thu được: F[i, j] = V[i] + F[i - 1, j - W[i]]
Vì theo cách xây dựng F[i, j] là giá trị lớn nhất có thể, nên F[i, j] sẽ là Max trong 2 giá
trị thu được ở trên.
Cơ sở quy hoạch động:
Dễ thấy F[0, j] = giá trị lớn nhất có thể bằng cách chọn trong số 0 gói = 0.
Tính bảng phương án:

procedure Optimize;
var
i, j: Integer;
begin
FillChar(F[0], SizeOf(F[0]), 0);
for i := 1 to n do
for j := 0 to M do
begin {Tính F[i, j]}
F[i, j] := F[i - 1, j];
if (j >= W[i]) and (F[i, j] < F[i - 1, j - W[i]] +
V[i]) then
F[i, j] := F[i - 1, j - W[i]] + V[i];
end;
end;
procedure Trace;
var
fo: Text;
begin
Assign(fo, OutputFile); Rewrite(fo);
WriteLn(fo, F[n, M]);
while n 0 do
begin
if F[n, M] F[n - 1, M] then
begin
Write(fo, n, ' ');
M := M - W[n];
end;
Dec(n);
end;
Close(fo);


   
7
6
5
5
4
4
3
3
4
3
2

0
1
2
1
3
2
3
2
1
2
2

0
0
0
1


mỗi học sinh nhận 0 phần thưởng). Ta cũng quy ước Chia(0, 0) = 1.
- Nếu số phần thưởng ít hơn số học sinh (i < j) thì trong mọi phương án chia, từ

học sinh thứ i + 1 trở đi sẽ không được nhận phần thưởng nào:
Chia(i, j) = Chia(i, i) nếu i < j.
Ta xét tất cả các phương án chia trong trường hợp i ≥ j. Ta tách các phương án chia
thành hai nhóm không giao nhau dựa trên số phần thưởng mà học sinh đứng cuối bảng
thành tích, học sinh thứ j, được nhận:
-

Nhóm thứ nhất gồm các phương án trong đó học sinh thứ j không được nhận

thưởng, tức là i phần thưởng chỉ chia cho j - 1 học sinh và do đó, số cách chia, tức là số
phần tử của nhóm này sẽ là: Chia(i, j - 1).
-

Nhóm thứ hai gồm các phương án trong đó học sinh thứ j cũng được nhận

thưởng. Khi đó, do học sinh đứng cuối bảng thành tích được nhận thưởng thì mọi học
sinh khác cũng sẽ có thưởng. Do ai cũng được thưởng nên ta bớt của mỗi người một
phần thưởng (để họ lĩnh sau), số phần thưởng còn lại (i - j) sẽ được chia cho j học sinh.
Số cách chia khi đó sẽ là Chia(i - j, j).
Tổng số cách chia cho trường hợp i ≥ j sẽ là tổng số phần tử của hai nhóm, ta có:
Chia(i, j) = Chia(i, j - 1) + Chia(i - j, j).
Tổng hợp lại ta có:

Điều kiện
i: số phần thưởng
j: số học sinh

else {i >= j > 0 }
Chia := Chia(i,j-1)+Chia(i-j,j);
end;
Phương án này chạy chậm vì phát sinh ra quá nhiều lần gọi hàm trùng lặp. Bảng
dưới đây liệt kê số lần gọi hàm Chia khi giải bài toán chia thưởng với bảy phần thưởng
(m = 7) và 4 học sinh (n = 4). Thí dụ, hàm Chia(1,1) sẽ được gọi 9 lần,… Tổng số lần
gọi hàm Chia là 79. 79 lần gọi hàm để sinh ra kết quả 11 là quá tốn kém.




















0
9
1

0
0
1
1
1
1
1
Số lần gọi hàm Chia cục
bộ
khi tính hàm Chia(7,4)

16


Sáng kiến kinh nghiệm 2014 – Mai Hồng Kiên -THPT chuyên

Làm tốt
Phương án 1 khá dễ triển khai nhưng chương trình sẽ chạy rất lâu. Diễn tả đệ quy
thường trong sáng, nhàn tản, nhưng khi thực hiện sẽ sinh ra hiện tượng gọi lặp lại những
hàm đệ quy. Cải tiến là tránh những lần gọi lặp như vậy. Muốn thế chúng ta tính sẵn các
giá trị của hàm theo các trị của đầu vào khác nhau và điền vào một mảng hai chiều cc.
Mảng cc được mô tả như sau:
const
MN = 70;{ gioi han tren cua m va n }

j-1

var cc: array[0..MN,0..MN] of longint;
Ta quy ước cc[i, j] chứa số cách chia i phần thưởng cho
j học sinh.


Sáng kiến kinh nghiệm 2014 – Mai Hồng Kiên -THPT chuyên

cc[0,0] := 1;
for i := 1 to m do cc[i,0] := 0;
for j := 1 to n do
begin
for i := 0 to j-1 do cc[i,j] := cc[i,i];
for i := j to m do
cc[i,j] := cc[i,j-1]+cc[i-j,j];
end;
Chia2 := cc[m,n];
end;
2.4.

Hiệu quả của SKKN.

- Trong quá trình trao đổi, thảo luận, trình bày học sinh được thể hiện khả năng vận
dụng, hiểu biết của mình nên các em tỏ ra hăng hái trong việc giơ tay phát biểu tranh
luận.
- Đa số học sinh các lớp 11Toán, 11A1 nắm được “phương pháp quy hoạch động” và
100% học sinh đội tuyển nắm và vận dụng tốt kĩ thuật này.
- Kết quả đạt được: Trong các năm học trước 2011-2012, 2012-2013 đội tuyển Tin học
của trường không có giải HSGQG nào thì đến năm học 2013-2014 đội tuyển Tin học
của trường đạt 8 giải HSG cấp tỉnh trong đó có giải nhất và giải nhì. 01 giải HSG Quốc
gia.

18




Chủ biên
Chủ biên
Chủ biên

19