SỞ GD&ĐT NGHỆ AN
TRƯỜNG THPT CON CUÔNG
………………………
SÁNG KIẾN KINH NGHIỆM
NÀ M
TÊN ĐỀ TÀI:
PHƯƠNG PHÁP QUY HOẠCH ĐỘNG VÀ ỨNG DỤNG VÀO GIẢI MỘT SỐ BÀI TOÁN BỒI DƯỠNG HỌC SINH GIỎI, THI CHUYÊN BẰNG NGÔN NGỮ LẬP TRÌNH PASCAL VÀ C++
Nhóm tác giả:
1. Đặng Văn Hảo
2. Ngô Thị Thanh Huyền
3. Phan Thị Thuý An
Lĩnh vực: Tin học
Đơn vị: Trường THPT Con Cuông
2
Con Cuông - Năm 2022
MỤC LỤC
Phần I. Đặt vấn đề: ................................................................................................. 5 1. Lí do chọn đề tài ................................................................................................. 5
2. Mục đích nghiên cứu, đóng góp mới của đề tài ............................................... 5 3. Đối tượng nghiên cứu .......................................................................................... 6 4. Phương pháp nghiên cứu ................................................................................... 6 5. Phạm vi nghiên cứu ............................................................................................ 6 6. Cấu trúc của đề tài .............................................................................................. 6
1. Cơ sở lý luận ................................................................................................... 6 2. Cơ sở thực tiễn ................................................................................................ 6 Phần II. Nội dung: ................................................................................................... 7 1. Cơ sở lý luận......................................................................................................... 7 1. 1. Giới thiệu .................................................................................................... 7
1. 2. Phương pháp quy hoạch động .................................................................... 7 1.2.1. Khái niệm ............................................................................................. 7 1.2.2. Đặc điểm chung của phương pháp quy hoạch động ............................. 9 1.2.3. Các bước giải bài toán bằng quy hoạch động ....................................... 9
1. 3. Cách tiếp cận quy hoạch động .................................................................... 9 1. 4. Lớp các bài toán được giải bằng quy hoạch động ..................................... 9 1. 5. Ưu điểm và hạn chế của quy hoạch động ................................................. 10 1.5.1. Ưu điểm ............................................................................................... 10 1.5.2. Hạn chế................................................................................................ 10
2. Cơ sở thực tiễn ................................................................................................... 10 2.1. Thực trạng của vấn đề trước khi áp dụng đề tài ........................................ 11 2.1.1. Đặc điểm tình hình .............................................................................. 11 2.1.2. Thực trạng trước khi nghiên cứu ........................................................ 11 2.1.3. Các giải pháp giải quyết vấn đề .......................................................... 12
2.2. Rèn luyện kỹ năng vận dụng phương pháp Quy hoạch động để giải một số bài toán cơ bản đến nâng cao ........................................................................... 12 2.2.1. Bài toán 1. Tìm dãy con không giảm nhiều phần tử nhất ................... 12 2.2.2. Bài toán 2. Dãy con chung dài nhất ................................................... 15 2.2.3. Bài toán 3. dãy con có tổng bằng s ..................................................... 19
2.2.4. Bài toán 4. chia kẹo ............................................................................. 23 3
2.2.5. Bài toán 5: Xếp đồ vật vào ba lô (mỗi vật có số lượng hạn chế) ........ 27
2. 3. Hướng dẫn giải một số bài toán bằng quy hoạch động ............................ 32 2.3.1. Bài toán 1. xâu con chung dài nhất ..................................................... 32 2.3.2. Bài toán 2. Cho thuê máy .................................................................... 33 2.3.3. Bài toán 3. Rô bốt ............................................................................... 35 2.4. Một số bài toán áp dụng phương pháp quy hoạch động tự giải ............... 36
2.4.1. Bài 1: Tổng lớn nhất ........................................................................... 36 2.4.2. Bài toán 2: Phân tích ........................................................................... 37 2.4.3. Bài toán 3: Bố trí phòng họp ............................................................... 38 2.4.4. Bài toán 4: Nối điểm ........................................................................... 38 2.4.5. Bài toán 5: Tính tổng của dãy số ........................................................ 39
2.4.6. Bài toán 6: Dãy Con lớn nhất đan dấu ................................................ 40 2.4.7. Bài toán 7: Sắp xếp xâu ...................................................................... 40 2.4.8. Bài toán 8: Tìm mật khẩu .................................................................... 41 2.4.9. Bài toán 9: TWOVALS ...................................................................... 41 2.5. So sánh kết quả trước và sau khi áp dụng phương pháp Quy hoạch động vào việc bồi dưỡng ........................................................................................... 42 2.5.1. Trước khi áp dụng phương pháp Quy hoạch động vào việc bồi dưỡng học sinh giỏi .................................................................................................. 42 2.5.2. Sau khi áp dụng phương pháp Quy hoạch động vào việc bồi dưỡng học sinh giỏi .................................................................................................. 43 Phần III. Kết luận: ................................................................................................ 45
1. Kết Luận ............................................................................................................. 45 1.1 Với mục tiêu đặt ra đề tài đã làm được: .................................................... 45 1.2. Hướng phát triển của đề tài: ..................................................................... 45 2. Một số kiến nghị đề xuất .................................................................................. 46 TÀI LIỆU THAM KHẢO .................................................................................... 47
4
PHỤ LỤC ............................................................................................................... 48
Phần I. Đặt vấn đề
1. Lí do chọn đề tài
Tự học tập, nghiên cứu là một nhiệm vụ quan trọng của mỗi giáo viên để nâng cao trình độ chuyên môn, phục vụ cho công tác giảng dạy và đặc biệt là trong bồi dưỡng đội tuyển học sinh giỏi.
Trong những năm gần đây, trong các đề thi học sinh giỏi tỉnh, quốc gia cũng như các bài tập trên các trang giải bài trực tuyến vn.spoj.com, vnoi.info, … có nhiều bài tập nếu chúng ta sử dụng những kiến thức cơ bản như đệ quy, duyệt, chia để trị, … có thể giải quyết được nhưng gặp nhiều khó khăn về mặt tốc độ cũng như giới hạn dữ liệu. Trong khi đó nếu chúng ta sử dụng phương pháp quy hoạch động hoặc các phương pháp trên có kết hợp với quy hoạch động thì cho một hiệu quả cao.
Quy hoạch động là một phương pháp rất hiệu quả để giải lớp bài toán trong Tin học. Đặc biệt là những bài toán tối ưu, khi sử dụng phương pháp quy hoạch động chương trình chạy nhanh, cách viết chương trình rõ ràng. Nhưng không phải bài toán nào cũng có thể áp dụng được bằng phương pháp quy hoạch động. Vậy thường những bài toán như thế nào thì áp dụng được phương pháp quy hoạch động và cách giải một bài toán quy hoạch động như thế nào là một vấn đề?
Mặt khác hiện nay khi bồi dưỡng thi học sinh giỏi giáo viên có thể lựa chọn 1 trong 3 ngôn ngữ lập trình là Pascal, C++ hoặc là Python. Pascal là ngôn ngữ lập trình đã cũ, câu lệnh dài và không được hỗ trợ nhiều. Python là ngôn ngữ lập trình mới nhất, câu lệnh ngắn gọn, hỗ trợ nhiều trong khi viết chương trình. Tuy nhiên một số bài toán khi chạy chương trình còn hạn chế về mặt thời gian. Chính vì vậy hiện nay thi học sinh giỏi thì ngôn ngữ lập trình C++ được lựa chọn nhiều nhất. Cho nên trong đề tài này tôi sử dụng ngôn ngữ lập trình C++ để viết chương trình cũng như minh hoạ thuật toán. Ngoài ra tôi còn minh hoạ chương trình bằng ngôn ngữ lập trình Pascal (Link code minh hoạ bằng ngôn ngữ lập trình pascal để ở phần phụ lục của đề tài) cho một số bạn đọc dễ hiểu và nắm bắt tốt hơn khi chưa tiếp cận nhiều với ngôn ngữ lập trình C++.
Vì những lý do trên, với những kinh nghiệm và tìm hiểu của bản thân, tôi đưa ra đề tài “phương pháp quy hoạch động và ứng dụng vào giải một số bài toán bồi dưỡng học sinh giỏi, thi chuyên bằng ngôn ngữ lập trình Pascal và C++” .
2. Mục đích nghiên cứu, đóng góp mới của đề tài
- Đề tài nêu ra các định hướng giúp học sinh có thể tiếp cận phương pháp Quy
hoạch động để giải một số bài toán tối ưu phù hợp với dữ liệu bài toán.
- Giúp người đọc tiếp cận ngôn ngữ lập trình C++ tốt hơn trong khi lập trình.
5
- Từ đó bồi dưỡng học sinh năng lực giải quyết vấn đề trong giải toán Tin học, đồng thời rèn luyện và nâng cao kĩ năng lập trình cho các em. Đặc biệt là học sinh
tham gia dự thi học sinh giỏi cấp tỉnh THCS, THPT, thi Olimpic Tin học trẻ hoặc thi vào các trường chuyên.
- Đối tượng nghiên cứu là học sinh giỏi tin, giáo viên giảng dạy, bồi dưỡng
3. Đối tượng nghiên cứu
- Phương pháp quy hoạch động và các bài toán tối ưu.
học sinh giỏi môn Tin trong trường THCS và THPT.
4. Phương pháp nghiên cứu
Để hoàn thành nhiệm vụ, tôi đã nghiên cứu rất nhiều sách và các chuyên đề Tin học dành cho học sinh Chuyên tin, những vấn đề cơ bản nhất về cấu trúc dữ liệu, thuật toán và cài đặt chương trình.
Cùng nhau trao đổi, thảo luận, rút kinh nghiệm cùng các đồng nghiệp trong
và ngoài trường nhằm nâng cao chất lượng cho đề tài.
Lựa chọn một số bài toán giải bằng phương pháp Quy hoạch động trong các
đề thi và chương trình tin học chuyên THPT.
5. Phạm vi nghiên cứu
Lí thuyết về Quy hoạch động và một số bài tập ứng dụng kĩ thuật xử lí Quy hoạch động hiệu quả trong các đề thi học sinh giỏi, các bài tập trên các trang trực tuyến như: vn.spoj.com, vnoi.info, laptrinh.ntu.edu.vn, chuyentin.pro…
6. Cấu trúc của đề tài
Ngoài phần mở đầu, kết luận và kiến nghị, phần nội dung đề tài gồm có 2
nội dung:
1. Cơ sở lý luận
Giới thiệu về phương pháp Quy hoạch động, các bước tiếp cận với phương pháp Quy hoạch động, cách nhận diện xem bài toán tối ưu nào có thể giải bằng phương pháp Quy hoạch động và nếu giải thì cách giải như thế nào? Trình bày các dạng, phân tích và cài đặt chương trình cụ thể để bạn đọc dễ hiểu nhất. Qua đó có thể vận dụng để giải quyết các bài toán về sau.
2. Cơ sở thực tiễn
6
Nêu ra thực trạng vấn đề, những hạn chế, khó khăn của học sinh cũng như giáo viên trong việc giải quyết các bài toán lớn, các bài toán ôn thi học sinh giỏi hiện nay. Qua đó giải quyết vấn đề và đưa ra các bài toán điển hình để so sánh sử dụng phương pháp Quy hoạch động và một số phương pháp khác. Sử dụng phương pháp Quy hoạch động có thể vận dụng lập trình giải các bài toán trong các đề thi hay khi ôn luyện. Trang bị kiến thức cho học sinh và giáo viên để giải quyết tốt khi gặp các bài toán có liên quan đến sử dụng phương pháp Quy hoạch động một cách hiệu quả nhất.
Phần II. Nội dung:
1. Cơ sở lý luận
Giới thiệu về phương pháp Quy hoạch động, các bước tiếp cận với phương pháp Quy hoạch động, cách nhận diện xem bài toán tối ưu nào có thể giải bằng phương pháp quy hoạch động và nếu giải thì cách giải như thế nào? Trình bày các dạng, phân tích và cài đặt chương trình cụ thể để bạn đọc dễ hiểu nhất. Qua đó có thể vận dụng để giải quyết các bài toán về sau.
1. 1. Giới thiệu
Phương pháp quy hoạch động do nhà toán học người Mỹ Richard Bellman
(1920 – 1984) phát minh năm 1953.
Phương pháp quy hoạch động (dynamic programming) là một kỹ thuật được
áp dụng để giải nhiều lớp bài toán, đặc biệt là bài toán tối ưu.
Vậy bài toán tối ưu là gì?. Đó chính là bài toán có nhiều nghiệm chấp nhận được mỗi nghiệm có một giá trị đánh giá. Mục tiêu đặt ra là tìm nghiệm tối ưu, đó là nghiệm có giá trị đánh giá nhỏ nhất hoặc lớn nhất (tối ưu).
Khi tiến hành giải một bài toán phức tạp (bài toán lớn) ban đầu người ta thường đi chia bài toán đó thành các bài toán con độc lập đơn giản để giải, khi tiến hành giải xong các bài toán con ta tổng hợp lời của các bài toán con và đó chính là bài toán lớn cần giải. Đây chính là phương pháp chia để trị được sử dụng rất thông dụng trong quá trình lập trình giải các bài toán trong Tin học. Nhưng đối với những bài toán phức tạp nếu chúng ta sử dụng phương pháp này thì sẽ mất test ở những dữ liệu lớn. Vì chưa tối ưu về mặt thời gian. Chính vì vậy phương pháp Quy hoạch động ra đời nhằm cải tiến về vấn đề này.
1. 2. Phương pháp quy hoạch động
1.2.1. Khái niệm
Phương pháp quy hoạch động là một kỹ thuật nhằm đơn giản hóa việc tính toán các công thức truy hồi bằng cách lưu toàn bộ hay một phần kết quả tính toán của mỗi bước trước đó với mục đích sử dụng lại (Công thức truy hồi là công thức thể hiện quan hệ giữa các bước trong một bài toán và kết quả của các bước sau thường dựa vào kết quả của các bước trước đó. Kết quả của bước cuối cùng chính là kết quả bài toán cần tìm).
Vậy bản chất của quy hoạch động =Chia để trị+Mảng (Lưu lại kết quả)
7
Phương pháp quy hoạch động sử dụng nguyên lý bottom - up, nghĩa là “ đi từ dưới lên”. Đầu tiên ta phải giải các bài toán con đơn giản nhất, có thể tìm ngay ra nghiệm. Sau đó kết hợp các bài toán con này lại để tìm lời giải cho bài toán lớn hơn và cứ như thế cho đến khi giải được bài toán yêu cầu. với phương pháp này mỗi bài toán con sau khi giải xong đều được lưu trữ lại và đem ra sử dụng nếu cần. Khi đó sẽ tiết kiệm được bộ nhớ và thời gian thực hiện.
Ngược lại phương pháp đệ quy giải quyết bài toán theo hướng top – down, nghĩa là để giải bài toán ban đầu, ta phải đi giải các bài toán con của nó. Đây là một phương pháp hay, tuy nhiên phương pháp này sẽ gặp một số hạn chế về mặt thời gian , tốc độ do phải tính toán nhiều lần một số bài toán con giống nhau nào đó. Để thấy rõ hơn ta đi tìm hiểu ví dụ sau:
Xét ví dụ 1: dãy Fibonacci là dãy số nguyên sau:
F0= 1, F1= 1,
Fn = Fn-1+Fn-2 với mọi n>=2
Hãy tính F5
Cách 2 Cách 1
#include
main() int f(int n)
{ {
int i,f[10]; int t;
f[1]=f[0]=1; if (n<2) return 1;
else return f(n-1)+f(n-2);
for(i=2;i<=5;i++) f[i]=f[i-1]+f[i-2];
cout<<"fib thu 5 la "< getch(); main() } { int n; cout<<"fib thu 5
la"< } 8 Cách 1: viết hàm đệ quy f(n) để tính số Fibonacci thứ n. Chương trình chính
gọi f(5) nó sẽ gọi đến f(4) và f(3) để tính… quá trình tính toán có thể vẽ như cây
sau : Như vậy để tính được f(5) máy tính phải thực hiện mất 1 lần f(4), 2 lần f(3), 3
lần f(2), 2 lần f(1). Nhưng cách 2 thì không như vậy nó tính f(1), f(2) từ đó tính
f(3), và tính được f(4), f(5). Khi đó mỗi giá trị chỉ phải tính một lần và cần lấy f[i]
nào thì lấy ra. - Quy hoạch động bắt đầu từ việc giải tất cả các bài toán nhỏ nhất (bài toán cơ
sở) để từ đó từng bước giải quyết bài toán lớn hơn cho tới khi giải được bài toán
lớn nhất là bài toán ban đầu. - Quy hoạch động cần có bảng phương án: chính là không gian lưu trữ lời giải
các bài toán con để tìm cách phối hợp chúng, đây là bảng phương án của quy
hoạch động. Thường kết quả cuối cùng của bảng phương án chính là kết quả của
bài toán cần tìm. 1.2.2. Đặc điểm chung của phương pháp quy hoạch động 1.2.3. Các bước giải bài toán bằng quy hoạch động Bước 1: Giải tất các bài toán cơ sở (thường là dễ nhất). lưu các lời giải vào bảng phương án. Đây là điều kiện dừng của bài toán Bước 2: Xây dựng công thức truy hồi : bằng cách phối hợp những lời giải của
bài toán nhỏ hơn đã lưu trong bảng phương án để tìm lời giải của bài toán lớn hơn
(công thức truy hồi) và lưu vào bảng phương án, nhờ có công thức truy hồi này ta
tính được bảng phương án. Bước 3: Dựa vào bảng phương án, ta truy vết tìm nghiệm tối ưu. Đây chính là kết quả của bài toán. 1. 3. Cách tiếp cận quy hoạch động Quy hoạch động thường dùng một trong 2 cách tiếp cận sau : - Tiếp cận từ dưới lên (Bottom up) Là phương pháp đi từ cái riêng đến cái chung, từ các thành phần ở mức cao
tới các đối tượng thành phần ở mức thấp, từ mức đơn vị chương trình tới mức tổng
thể. - Tiếp cận từ trên xuống ( Top down) Là phương pháp phân rã vấn đề có hệ thống từ trên xuống. Cách tiếp cận từ dưới lên hiệu quả hơn từ trên xuống nên cách tiếp cận từ dưới lên được sử dụng nhiều hơn. 1. 4. Lớp các bài toán được giải bằng quy hoạch động Nhưng không phải bài toán tối ưu nào cũng giải được bằng phương pháp quy - Khi bài toán có tính chất truy hồi. 9 hoạch động. Thường những bài toán có đặc điểm sau: - Bài toán lớn phải phân rã được thành nhiều bài toán con, mà sự phối hợp lời giải của các bài toán con đó cho ta lời giải của bài toán lớn. - Có thể lưu trữ nghiệm của các bài toán con dưới một hình thức nào đó để - Quá trình từ bài toán cơ sở tìm ra lời giải bài toán ban đầu phải qua hữu hạn phối hợp tìm nghiệm của bài toán lớn. - Kích thước của bài toán lớn. bước. 1. 5. Ưu điểm và hạn chế của quy hoạch động - Qua phân tích ở ví dụ 1 ta thấy được ưu điểm của quy hoạch động là tiết
kiệm được thời gian thực hiện vì không cần phải tính đi tính lại nhiều lần một số
bài toán con giống nhau. - Ngoài ra lời giải của bài toán sử dụng quy hoạch động thường gắn gọn, sáng 1.5.1. Ưu điểm sủa, có tính chất lời giải cao. - Việc tìm công thức truy hồi không phải dễ tìm. Để tìm được đòi hỏi sự phân
tích tổng hợp rất công phu, khó nhận ra được như thế nào là chính xác nên mất
nhiều thời gian để suy nghĩ. - Khi lưu bảng lưu trữ đòi hỏi mảng hai chiều, ba chiều…thì khó có thể xử lý
dữ liệu với kích thước cỡ mỗi chiều lớn đến hàng trăm. Và còn bị hạn chế về bộ
nhớ vì ta phải lưu trữ nghiệm của các bài toán con. - Không phải lúc nào kết hợp lời giải các bài toán con cũng được kết quả của
bài toán lớn mà ta còn phải biết sử dụng và phối hợp uyển chuyển nhiều thuật toán,
không được lạm dụng hay coi thường bất cứ một phương pháp nào. - Có những bài toán không thể giải được bằng quy hoạch động. 1.5.2. Hạn chế 2. Cơ sở thực tiễn 10 Nêu ra thực trạng vấn đề, những hạn chế, khó khăn của học sinh cũng như
giáo viên trong việc giải quyết các bài toán lớn, các bài toán ôn thi học sinh giỏi
hiện nay. Qua đó giải quyết vấn đề và đưa ra các bài toán điển hình để so sánh sử
dụng phương pháp Quy hoạch động và một số phương pháp khác. Sử dụng phương
pháp Quy hoạch động có thể vận dụng lập trình giải các bài toán trong các đề thi
hay khi ôn luyện. Trang bị kiến thức cho học sinh và giáo viên để giải quyết tốt khi
gặp các bài toán có liên quan đến sử dụng phương pháp Quy hoạch động một cách
hiệu quả nhất. 2.1. Thực trạng của vấn đề trước khi áp dụng đề tài 2.1.1. Đặc điểm tình hình * Thuận lợi: - Với sự bùng nổ của ngành công nghệ thông tin cũng như chương trình giáo dục phổ thông 2018 các em học sinh, phụ huynh ngày càng quan tâm hơn. - Ngày nay số lượng học sinh có máy tính cá nhân ngày càng nhiều, các em có điều kiện để học tập, nghiên cứu và lập trình được nhiều hơn. - Các cuộc thi lập trình này ngày càng tổ chức nhiều hơn, việc học, xem tài
lệu cũng dễ dàng hơn, có thể xem các tài liệu trên web cũng như các kênh như
youtube…. * Khó khăn: - Do môn Tin học chưa có trong tổ hợp môn thi tốt nghiệp và đại học nên
các em và phụ huynh chưa quan tâm đến nên việc chọn học sinh giỏi cũng như
các em chưa thực sự đầu tư chuyên sâu vào lập trình. - Những kiến thức trong chương trình Tin học phổ thông còn hạn chế, hoặc
chưa đủ đáp ứng cho việc giải một số bài toán trong các kỳ thi học sinh giỏi
Tỉnh khi có yêu cầu dữ liệu lớn cùng thời gian thực hiện ngắn. - Các tài liệu tổng hợp các cách để giải quyết các bài toán yêu cầu cao như vậy chưa có nhiều để học sinh tham khảo, ôn luyện. 2.1.2. Thực trạng trước khi nghiên cứu Ngày nay công nghệ thông tin là một trong những ngành hót, nhân lực còn
thiếu, mỗi năm sinh viên ra trường chưa đáp ứng đủ yêu cầu thị trường, mức thu
nhập nghành công nghệ thông tin là khá cao, nên việc quan tâm của các em ngày
càng nhiều, nhất là trong các cuộc thi lập trình. Năm học này thì trường đại học và khoa học công nghệ Hà Nội đã có 9 ngành cho học sinh đăng kí thi tổ hợp môn: Toán , Lý, Tin Với sự phát triển nhanh về tốc độ cũng như sự quan tâm đến của nghành công
nghệ thông tin ngày càng cao thì đề thi học sinh giỏi Tin học cũng đòi hỏi ngày càng
nâng cao hơn. Trong các đề thi học giỏi thì người ta quan tâm về thời gian thực
hiện và độ lớn của dữ liệu đầu vào. Đa số giáo viên gặp khó khăn trong việc hướng
dẫn học sinh giải bài toán thế nào để đạt được trọn vẹn yêu cầu của bài toán. 11 Đối với những bài toán phức tạp và có dữ liệu lớn thì giáo viên và học sinh
còn gặp khó khăn, chưa giải quyết vấn đề một cách triệt để. Dẫn đến sẽ mất test.
Chương trình chưa tối ưu chỉ ăn test với dữ liệu nhỏ. 2.1.3. Các giải pháp giải quyết vấn đề Có những bài toán nhiều khi có vẻ đơn giản, đa số học sinh có thể giải được
nhưng khi thực hiện với dữ liệu lớn thì không đáp ứng được thời gian yêu cầu hoặc
không thể thực hiện được tất cả các test yêu cầu. Lúc này đòi hỏi phải tìm được thuật
toán tối ưu nhất. Đa số khi chấm bài, dùng test chấm mới biết được chương trình đáp ứng được
bao nhiêu test so với yêu cầu của đề ra. Điều này chỉ thực hiện được khi ôn luyện
cho các em, còn khi các em đi thi thì không tự ước lượng được bài làm đạt kết quả
thế nào. Thuật toán Quy hoạch động không gì khác hơn là một sự tối ưu hóa của các
kỹ thuật. Nó làm giảm sự phức tạp về thời gian bằng cách sử dụng một số loại thứ
tự thay vì nhất thiết phải sắp xếp dữ liệu. Qua đó giúp chương trình chạy nhanh
hơn, không gian lưu trữ ít hơn. Hiện nay trong các kì thi học sinh giỏi và thi vào trường chuyên, đề thi
thường có những bài toán mà sử dụng phương pháp Quy hoạch động để giải quyết
vấn đề mới tối ưu. Chính vì vậy giáo viên và học sinh nắm rõ phương pháp Quy
hoạch động là một lợi thế rất lớn khi lập trình giải những bài toán phức tạp và dữ
liệu lớn. Như vậy sẽ đạt kết quả cao hơn trong các kì thi học sinh giỏi nói chung và
thi vào trường chuyên nói riêng Và trong đề tài này tôi đã trình bày các kiến thức và kĩ năng từ đó vận dụng
phương pháp Quy hoạch động để xử lý những bài toán như vậy. Sau khi đọc hiểu
về mặt lý thuyết thì người đọc có thể thực hành làm những bài tập điển hình có
code, có hướng dẫn. Qua đó sẽ tự tin hơn, tư duy và kỹ năng tốt hơn, nắm rõ và có
thể vận dụng để lập trình giải những bài toán cùng dạng sau này. 2.2. Rèn luyện kỹ năng vận dụng phương pháp Quy hoạch động để giải một số
bài toán cơ bản đến nâng cao 2.2.1. Bài toán 1. Tìm dãy con không giảm nhiều phần tử nhất Cho dãy số nguyên có n phần tử a1, a2, ..., an . Một dãy con không giảm của
dãy đã cho là dãy các phần tử còn lại của dãy đó sau khi ta xóa bỏ một hoặc một số
phần tử bất kì của nó, các phần tử của dãy con tạo thành không giảm. Ví dụ: dãy 1,
4, 10, 11, 12 là một dãy con không giảm của 1, 4, 10, 9, 8, 17, 11, 7, 12, 6. * Yêu cầu: Tìm dãy con không giảm của dãy a gồm nhiều phần tử nhất. * Dữ liệu vào: từ file văn bản DAYCON.INP gồm 2 dòng: - Dòng tiếp theo, ghi các số nguyên của dãy N số nguyên a1, a2,...,an - Dòng đầu tiên ghi số N (0 12 mỗi số cách nhau một dấu cách. - Số max là độ dài dãy con không giảm dài nhất tìm được - Chỉ số xuất hiện của các số hạng của dãy con trong dãy đã cho. * Kết quả: ghi ra file văn bản DAYCON.OUT gồm 2 dòng: * Ví dụ: DAYCON.INP DAYCON.OUT 10 5 6 5 8 12 6 9 7 13 2 13 6 8 12 13 13 *Cách giải: Gọi l[i] là độ dài dãy con không giảm dài nhất, các phần tử lấy trong miền từ an đến ai và phần tử bắt đầu là a[i] (i=n, n-1,..., 0). Bài toán sử dụng thêm 2 phần tử: a[0]= -32768 và a[n+1]=32767 chắc chắn
thuộc dãy con không giảm dài nhất. Khi đó độ dài dãy con không giảm dài nhất bắt
đầu từ a[n+1] là 1, dãy bắt đầu từ a[i], ..., a[n+1]; Bước 1: Giải các bài toán cơ sở và lưu vào bảng phương án L[n+1]=1; với a[n+1]=32767 nên chắc chắn thuộc dãy con không giảm dài nhất. Bước 2: Tìm công thức truy hồi Khi xét tới phần tử a[i] thì a[i] phải nối vào đầu 1 dãy con không giảm mà bắt đầu phần tử a[j] nào đó phải thõa mãn a[i]<=a[j] (j=i+1,...,n+1). Nhưng trong đó các a[j]>=a[i] thì ta phải chọn jmax để dãy con không giảm bắt đầu từ a[jmax] dài nhất. Nên công thức truy hồi của bài toán là: L[i]=max{l[j] | j=i+1,..., n+1 thõa mãn a[i]<=a[j]} +1 Bước 3: Dựa vào bảng phương án, ta truy vết tìm nghiệm tối ưu. * Tính bảng phương án: dựa vào giá trị l[n+1]=1 để tính tiếp l[i] (i= n, n- 1,...,0). Dùng t[i] để lưu lại các vị trí jmax. Xét ví dụ: N=10; a=(6 5 8 12 6 9 7 13 2 13) ta có bảng phương án 1 2 3 4 5 6 7 8 9 10 11 I 0 5 8 12 6 9 7 13 2 13 32767 A -32768 6 6 6 5 4 5 4 4 3 3 2 1 L 7 13 3 3 6 8 6 8 8 10 9 10 11 T 1 Đoạn code tính l[i] như sau: l[n+1]=1; t[n+1]=n+1; for (int i=n;i>=0;i--) { jmax=n+1; for (int j=i+1;j<=n+1;j++) if ((a[i]<=a[j])&&(l[j]>l[jmax])) jmax=j; l[i]=l[jmax]+1; t[i]=jmax; }
* Độ phức tạp của thuật toán: Với đoạn code trên thì dễ thấy chi phí không gian cài đặt trên là O(n), chi phí thời gian là O(n2). Với n là số phần tử của dãy. * Truy vết tìm ra các phần tử trong dãy: dựa vào mảng t[i] để đưa ra các phần tử thuộc dãy con không giảm dài nhất. Chương trình sau sẽ trình bày cụ thể. Chương trình hoàn chỉnh #include using namespace std; ifstream fi ("DAYCON.INP"); ofstream fo ("DAYCON.OUT"); int n,a[100],l[100],t[100]; void nhap() { fi>>n; a[0]=-32768; a[n+1]=32767; for (int i=1;i<=n;i++)
fi>>a[i]; } void qhd() 14 { int jmax; l[n+1]=1; t[n+1]=n+1; for (int i=n;i>=0;i--) { jmax=n+1; for (int j=i+1;j<=n+1;j++) if ((a[i]<=a[j])&&(l[j]>l[jmax])) jmax=j; l[i]=l[jmax]+1; t[i]=jmax; } } void Truyvet() fo < fo <<"\n"; int i=0; while (t[i]!=n+1) { fo < i=t[i]; } } main() { nhap(); qhd(); truyvet(); } 2.2.2. Bài toán 2. Dãy con chung dài nhất Cho dãy số nguyên a=(a1, a2,…,aM ), b=(b1, b2,…,bN ), với M, N <=100. Hãy tìm một dãy con chung c=(c1, c2,…,cK ) của a và b gồm nhiều số hạng
nhất. Dãy c nhận được bằng cách xóa đi một số hạng của dãy a, c cũng nhận được
bằng cách xóa đi một số số hạng của dãy b, sau khi xóa ở hai dãy giữ nguyên thứ
tự các phần tử còn lại * Dữ liệu vào: từ file văn bản DAYCC.INP gồm 3 dòng: - Dòng 2 ghi các số a1, a2,…,aM - Dòng 3 ghi các sô b1, b2,…,bN 15 - Dòng 1 ghi hai số nguyên M, N. - Dòng 1 ghi số K là số lượng các số hạng của dãy con chung c (nếu không * Dữ liệu ra: file văn bản DAYCC.OUT gồm: - Trong K dòng tiếp theo, dòng thứ i (i= 1, 2…, K) ghi hai số X, Y với ý
nghĩa là: Số hạng thứ i của dãy c là số hạng thứ X của dãy a và số hạng thứ Y
của dãy b. có dãy con chung ghi số 0 ) * Ví dụ: DAYCC.INP DAYCC.OUT 7 6 4 3 5 1 3 5 5 3 7 5 1 5 3 5 3 1 6 4 4 3 2 2 *Cách giải: Gọi l[i,j] là độ dài dãy con chung dài nhất khi xét tới phần tử a[i] (i=0,...,n) và
phần tử b[j] (j=0,...,m). Khi đó L[n,m] là độ dài dãy con chung dài nhất của an và
bm. Bước 1: Giải các bài toán cơ sở và lưu vào bảng phương án L[0,j]=0; dãy a không có phần tử nào, dãy b có j phần tử (j=0,...,m). Nên không có dãy con chung. L[i,0]=0; dãy b không có phần tử nào, dãy a có i phần tử (i=0,...,n). Nên không có dãy con chung. Bước 2: Tìm công thức truy hồi Khi xét tới l[i,j] (tức xét tới a[i] và b[j]) thì có hai khả năng: Khả năng 1: a[i]=b[j] khi đó độ dài dãy con chung được tăng lên một đơn vị L[i,j]=l[i-1,j-1]+1 (i=0,...,n; j=0,...,m) Khả năng 2: a[i] ≠ b[j] khi đó độ dài dãy con chung sẽ phụ thuộc giá trị của l[i,j-1] và l[i-1,j]. Do độ dài dãy con chung lớn nhất nên ta lấy max của chúng L[i,j]=max(l[i-1,j],[i,j-1]) (i=0,...,n; j=0,...,m) * Bảng phương án: dựa vào bài toán cơ sở và công thức truy hồi ở trên ta áp Bước 3: Dựa vào bảng phương án, ta truy vết tìm nghiệm tối ưu. 16 dụng cho ví dụ trên nên có bảng sau: Xét ví dụ trên ta có bảng phương án: L[i,j] 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 1 1 2 2 2 0 2 1 1 1 2 2 3 0 3 1 1 2 2 3 3 0 4 1 2 2 3 3 3 0 5 1 2 2 3 3 3 0 6 1 2 3 3 4 4 0 7 Đoạn code tính L[i,j]: for(int i=0;i<=n;i++) l[i][0]=0; for (int j=0;j<=m;j++) l[0][j]=0; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (a[i]==b[j]) l[i][j]=l[i-1][j-1]+1; else { if ( l[i-1][j]>l[i][j-1]) l[i][j]=l[i-1][j]; else l[i][j]=l[i][j-1]; * Độ phức tạp của thuật toán: Với đoạn code trên thì dễ thấy chi phí không
gian cài đặt trên là O(nm), chi phí thời gian là O(nm). Với n là số phần tử của dãy
a, m là số phàn tử của dãy b. * Truy vết tìm kết quả: L[n,m] chính là độ dài dãy con chung dài nhất. để
đưa ra vị trí của các phần tử trong dãy ta xét: nếu a[i]=b[j] thì đưa ra vị trí i, j
ngược lại thì không đưa ra. Cụ thể trong chương trình sau: 17 } Chương trình hoàn chỉnh #include using namespace std; ifstream fi("DAYCC.INP ");
ofstream fo("DAYCC.OUT "); int n,m,l[100][100],a[100],b[100],c[100];
void nhap() { fi>>n>>m; for (int i=1;i<=n;i++) fi>>a[i]; for (int j=1;j<=m; j++) fi>>b[j]; } void qhd() { for(int i=0;i<=n;i++) l[i][0]=0; for (int j=0;j<=m;j++) l[0][j]=0; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (a[i]==b[j]) l[i][j]=l[i-1][j-1]+1; else { if ( l[i-1][j]>l[i][j-1]) l[i][j]=l[i-1][j]; else l[i][j]=l[i][j-1]; } } void truyvet() { fo < fo <<"\n"; int i,j; i=n; j=m; while ((i!=0)&&(j!=0)) if (a[i]==b[j]) { 18 { fo < i--; j--; } else if (l[i][j]==l[i-1][j]) i--; else j--; } } int main() { nhap(); qhd(); truyvet(); } 2.2.3. Bài toán 3. dãy con có tổng bằng s Cho dãy a1, a2,…, an. Tìm một dãy con có tổng bằng S. - Dòng đầu tiên là 2 số N, S (N<=200); - Dòng thứ 2 là N số ai (i=1, 2,..., N; -32000<=ai<=32000). * Dữ liệu vào: từ file văn bản TONGS.INP gồm 2 dòng: * Kết quả: ghi ra flie văn bản TONGS.OUT có dạng: - Nếu không có đưa ra là 0 - Nếu có đưa ra các phần tử thuộc dãy con tìm được. * Ví dụ: TONGS.INP TONGS.OUT 11 1 5 12 1 11 2 4 6 *Cách giải: Gọi T[i,j] là tổng giá trị có thể có bằng cách chọn các vật {1,2,...,i} với giới hạn
trọng lượng j (j=0,...,s). Khi đó giá trị được chọn trong số n phần tử với giới hạn
giá trị là s chính là T[i,s] (i=0,...,n). Bước 1: Giải các bài toán cơ sở và lưu vào bảng phương án T[0,j]=0; (j=0,...,s) dãy số không có phần tử nào, 19 T[i,0]=0; (i=0,...,n) dãy số có i phần tử nhưng tổng s=0; Bước 2: Tìm công thức truy hồi Khi xét tới T[i,j] tức là xét tới phần tử a[i] và khối lượng lúc này là j, ta có 2 khả năng: Khả năng 1: phần tử a[i] sẽ được cộng vào tổng (tức lúc đó nếu chọn phần tử
a[i] vào thì tổng vẫn<=j). Khi đó giá trị T[i,j] là tổng lớn nhất có thể chọn các phần
tử i trong dãy {1, 2,...,i-1, i} với giới hạn trọng lượng j. T[i,j]:=T[i-1,j-a[i]]+a[i]; Khả năng 2: phần tử a[i] không được chọn (tức lúc đó nếu chọn phần tử i vào
thì >=j). Khi đó giá trị T[i,j] là tổng giá trị lớn nhất có thể chọn các phần tử {1,
2,...,i-1} với giới hạn trọng lượng j. T[i,j]:=T[i-1,j]; Bước 3: Dựa vào bảng phương án, ta truy vết tìm nghiệm tối ưu. *
hồi ở trên ta áp dụng cho ví dụ của bài thu được bảng sau: Tính bảng phương án dựa vào kết quả của bài toán cơ sở và công thức truy Xét ví dụ trên ta có bảng phương án: T[i,j] 0 1 2 3 4 5 6 7 8 9 10 11 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 2 0 1 1 1 1 1 1 1 1 1 1 11 12 3 0 1 2 3 3 3 3 3 3 3 3 3 3 4 0 1 2 3 4 5 6 7 7 7 7 7 7 5 0 1 2 3 4 5 6 7 8 9 10 11 12 Code để tính T[i,j]: for(int i=0;i<=n;i++) t[i][0]=0; for(int j=0;j<=s;j++) t[0][j]=0; for(int i=1;i<=n;i++) for(int j=1;j<=s;j++) if ((j>=a[i])&&(t[i-1][j-a[i]]+a[i]<=s)) 20 t[i][j]=t[i-1][j-a[i]]+a[i]; else * Độ phức tạp của thuật toán: Với đoạn code trên thì dễ thấy chi phí không
gian cài đặt trên là O(ns), chi phí thời gian là O(ns). Với n là số phần tử của dãy a,
s là tổng s. t[i][j]=t[i-1][j]; * Truy vết tìm kết quả: Theo bài thì ta sẽ lấy một giá trị T[i,s]=s bất kỳ, từ
đó truy vết ra các phần tử mà có tổng cộng lại bằng s. truy vết cụ thể trong chương
trình hoàn chỉnh dưới. Chương trình hoàn chỉnh #include using namespace std; ifstream fi ("TONGS.INP");
ofstream fo ("TONGS.OUT"); int a[100],n,s,t[100][100]; void nhap() { int i;
fi>>n>>s; for(i=1;i<=n;i++) fi>>a[i]; fi.close(); } void qhd() { for(int i=0;i<=n;i++)
t[i][0]=0; for (int j=0;j<=s;j++)
t[0][j]=0; for(int i=1;i<=n;i++) for(int j=1;j<=s;j++) if ((j>=a[i])&&(t[i-1][j-a[i]]+a[i]<=s)) t[i][j]=t[i-1][j-a[i]]+a[i]; else 21 t[i][j]=t[i-1][j]; } void truyvet() { int k=0; for(int i=1;i<=n;i++) if ( t[i][s]==s) { k=i;
break; } if (k==0) fo<<”0”; else while ( k!=0) { if (t[k][s]!=t[k-1][s])
{ fo < } k--; } } int main() { nhap(); qhd(); truyvet(); 22 } 2.2.4. Bài toán 4. chia kẹo Có N gói kẹo dánh số từ 1 đến N (0 - Dòng thứ nhất ghi số N. - Dòng thứ hai ghi các số lần lượt từ A1 đến AN. Các số ghi bắt đầu từ
đầu dòng theo thứ tự từ trái qua phải. * Dữ liệu vào: từ file KEO.INP gồm 2 dòng như sau: - Dòng đầu tiên ghi 3 số X, Y, Z, trong đó: X là số kẹo chênh lệch giữa
hai phần, Y là số kẹo của phần 1, Z là số kẹo của phần 2. - Dòng thứ 2 ghi số hiệu các phần thuộc phần 1 - Dòng thứ 3 ghi số hiệu các phần thuộc phần 2 * Dữ liệu ra: file KEO.OUT có cấu trúc gồm 3 dòng như sau: * Ví dụ: KEO.INP KEO.OUT 5 3 20 23 10 20 3 4 6 2 1 3 4 5 *Cách giải: Để chia các gói kẹo thành 2 phần sao cho tổng số kẹo trong hai phần chênh
lệch ít nhất ta tiến hành tính tổng toàn bộ số kẹo của các gói (sum), sau đó chia đôi
lấy phần nguyên (s=sum div 2). Khi đó bài toán trở thành tìm dãy con có tổng nhỏ
hơn hoặc bằng s. Phần thứ nhất sẽ là các phần tử trong dãy có tổng nhỏ hơn hoặc bằng s, phần thứ 2 sẽ là các phần tử còn lại (chắc chắn có tổng số kẹo lớn hơn hoặc bằng s). Độ lệch của hai phần sẽ là: tổng số kẹo của phần 2 trừ đi tổng số kẹo của phần
1. Gọi T[i,j] là tổng số kẹo của phầng 1 có thể có bằng cách chọn các gói
{1,2,...,i} với giới hạn trọng lượng j (j=0,...,s). Khi đó giá trị được chọn trong số n
gói với giới hạn là s chính là T[i,s] (i=0,...,n). Bước 1: Giải bài toán cơ sở và lưu vào bảng phương án 23 T[0,j]=0 ; (j=0,...,s) không có gói kẹo nào; T[i,0]=0; (i=0,...,n) có n gói kẹo, nhưng khối lượng j=0; Bước 2: Tìm công thức truy hồi Khi xét tới T[i,j] tức là xét tới gói kẹo thứ i (số kẹo a[i]) và tổng lúc này là j, ta có 2 khả năng: Khả năng 1: gói kẹo thứ i sẽ được cộng vào tổng (tức lúc đó nếu chọn phần tử
a[i] vào thì tổng vẫn<=j). Khi đó giá trị T[i,j] là tổng lớn nhất có thể chọn các gói i
trong dãy {1, 2,...,i-1, i} với giới hạn tổng j. T[i,j]=T[i-1,j-a[i]]+a[i]; Khả năng 2: phần tử a[i] không được chọn (tức lúc đó nếu chọn gói thứ i vào
thì >=j). Khi đó giá trị T[i,j] là tổng giá trị lớn nhất có thể chọn các gói {1, 2,...,i-1}
với giới hạn tổng j. T[i,j]:=T[i-1,j]; Bước 3 : Xây dựng bảng phương án và truy tìm kết quả Dựa vào các giá trị của bài toán cơ sở và kết hợp với công thức truy hồi ta tính được bảng phương án. Xét ví dụ trên ta có bảng phương án: T[i,j] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 2 0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 20 20 3 0 0 0 3 3 3 3 3 3 3 10 10 10 13 13 13 13 13 13 13 20 20 4 0 0 0 3 4 4 4 7 7 7 10 10 10 13 14 14 14 17 17 17 20 20 5 0 0 0 3 4 4 6 7 7 9 10 10 10 13 14 14 16 17 17 19 20 20 Đoạn code để tính T[i,j] là: for(int i=0;i<=n;i++) t[i][0]=0; for (int j=0;j<=s;j++) t[0][j]=0;
for(int i=1;i<=n;i++) for(int j=1;j<=s;j++) if ((j>=a[i])&&(t[i-1][j-a[i]]+a[i]>t[i-1][j])) t[i][j]=t[i-1][j-a[i]]+a[i]; else 24 t[i][j]=t[i-1][j]; Chương trình hoàn chỉnh #include using namespace std; ifstream fi ("KEO.INP");
ofstream fo ("KEO.OUT"); int a[100],n,lech,d1,d2; long s,sum,t[100][100]; int kt[100]; void nhap() { int i; fi>>n;
sum=0; for(i=1;i<=n;i++)
{ fi>>a[i]; sum=sum+a[i]; } s=sum/2.0;
fi.close(); } void qhd() { 25 for(int i=0;i<=n;i++) t[i][0]=0;
for (int j=0;j<=s;j++) t[0][j]=0;
for(int i=1;i<=n;i++) for(int j=1;j<=s;j++) if ((j>=a[i])&&(t[i-1][j-a[i]]+a[i]>t[i-1][j])) t[i][j]=t[i-1][j-a[i]]+a[i]; else t[i][j]=t[i-1][j]; } void truyvet() { fo < for(int i=1;i<=n;i++) kt[i]=0; int i=n; while (i!=0) { if (t[i][s]!=t[i-1][s]) { kt[i]=1; s=s-a[i]; } i--; } for(int i=1;i<=n;i++) if (kt[i]==1) fo < fo<<"\n"; for(int i=1;i<=n;i++) if (kt[i]==0) fo < } int main() { nhap(); qhd(); truyvet(); 26 } 2.2.5. Bài toán 5: Xếp đồ vật vào ba lô (mỗi vật có số lượng hạn chế) Một chiếc ba lô có thể chứa một khối lượng không quá M. Có N loại đồ vật
được đánh số từ 1 đến N, Mỗi đồ vật loại i có khối lượng Wi và giá trị Ci
(i=1,2,…,N) số lượng mỗi loại đồ vật là hạn chế. Hãy chọn các đồ vật để xếp vào
ba lô sao cho tổng giá trị các đồ vật trong ba lô là lớn nhất (nếu có thể xếp được). - Dòng đầu ghi 2 số nguyên dương N, M (0 - Dòng i+1 (1<=i<=N) ghi hai số nguyên dương Wi và Ci (0 * Dữ liệu vào: trong file BALO.INP gồm 2 dòng: 0 - Dòng đầu ghi tổng giá trị lớn nhất tìm được - Dòng thứ 2 ghi số hiệu các đồ vật được chọn. * Kết quả: đưa ra file BALO.OUT gồm 2 dòng: * Ví dụ: BALO.INP BALO.OUT 197 8 16 8 4 2 1 1 7 3 45 4 15 2 20 7 20 5 7 8 3 10 125 * Cách giải: Gọi T[i,j] là giá trị lớn nhất có thể có bằng cách chọn các vật {1,2,...,i} với
giới hạn trọng lượng j. Khi đó giá trị lớn nhất khi được chọn trong số n vật với giới
hạn khối lượng là W chính là T[N,M]. với W[i] là khối lượng vật thứ i, C[i] là giá
trị vật thứ i Bước 1: Giải tất các bài toán cơ sở. lưu các lời giải vào bảng phương án. 27 T[0,j]=0; là giá trị lớn nhất khi không chọn vật nào với giới hạn trọng lượng
j. Bước 2: Xây dựng công thức truy hồi Để chọn các vật 1,2,..., i-1,i vào túi với giới hạn khối lượng j khi đó sẽ có hai khả năng: Khả năng 1: vật thứ i không được chọn vào trong túi (tức lúc đó nếu chọn vật
i vào thì sức chứa của túi >j). Khi đó giá trị T[i,j] là giá trị lớn nhất có thể chọn các
vật {1, 2,...,i-1} với giới hạn trọng lượng j. T[i,j]:=T[i-1,j]; Khả năng 2: vật thứ i được chọn vào trong túi (tức lúc đó nếu chọn vật i vào
thì sức chứa của túi vẫn <=j). Khi đó giá trị T[i,j] là giá trị lớn nhất có thể chọn các
vật {1, 2,...,i-1,i} với giới hạn trọng lượng j. T[i,j]:=T[i-1,j-Wi]+Ci; Theo bài thì ta sẽ lấy giá trị T[i,j] lớn nhất trong 2 khả năng trên => T[i,j] :=max(T[i-1,j], T[i-1,j-Wi]+Ci) * Tính bảng phương án: Trong bảng phương án ta thêm dòng 0 và cột 0 nên
khi đó có N+1 dòng, M+1 cột, trước tiên ta điền cơ sở quy hoạch động, sau đó sử
dụng công thức truy hồi, dùng dòng 0 để tính dòng 1, dùng dòng 1 để tính dòng
2,..., đến khi tính hết dòng N. Bước 3: Dựa vào bảng phương án, ta truy vết tìm nghiệm tối ưu. Ví dụ minh họa : N=8, M=16 ; W= {1, 3, 4, 2, 7, 5, 8, 10} 28 C= {7, 45, 15, 20, 20, 7, 3, 125} Ta có bảng phương án : T[i,j] (i=0,1,...,8 ; j=0,1,...,16) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 1 0 7 52 52 52 52 52 52 52 2 0 7 7 4
5 5
2 5
2 5
2 5
2 5
2 5
2 67 67 67 67 67 67 67 3 0 7 1
5 4
5 5
2 5
2 5
2 6
0 6
7 6
7 87 87 87 87 87 87 87 4 0 7 2
0 4
5 5
2 6
5 7
2 7
2 7
2 8
0 5 0 7 2
0 4
5 5
2 6
5 7
2 7
2 7
2 8
0 87 87 87 92 92 92 10
0 6 0 7 2
0 4
5 5
2 6
5 7
2 7
2 7
2 8
0 87 87 87 92 92 92 10
0 7 0 7 2
0 4
5 5
2 6
5 7
2 7
2 7
2 8
0 87 87 87 92 92 92 10
0 8 0 7 2
0 4
5 5
2 6
5 7
2 7
2 7
2 8
0 12
5 13
2 14
5 17
0 17
7 19
0 19
7 Sau khi điền được bảng phương án ta có đoạn code tính T[i,j] sau : for (int j=0;j<=M ;j++) T[0][j]=0; for(int i=1;i<=N;i++) for (int j=0;j<=M;j++) if ((j>=W[i])&&(T[i-1][j] T[i][j]=T[i-1][j-W[i]]+C[i]; 29 else * Độ phức tạp của thuật toán: T[i][j]=T[i-1][j]; * Truy vết để tìm ra các vật được chọn Với đoạn code trên thì dễ thấy chi phí không gian cài đặt trên là O(nm), chi
phí thời gian cũng là O(nm). Với n là số đồ vật, M là sức chứa khối lượng của túi. Tính được bảng phương án ta biết ngay được giá trị của T[N,M] và đây chính
là giá trị lớn nhất khi chọn các i gói trong số N gói với giới hạn trọng lượng M.
Nếu T[N,M]=T[N-1,M] thì tức là không chọn gói thứ N, ta lại truy tiếp đến gói
T[N-1,M]. Còn nếu T[N,M] ≠ T[N-1,M] tức thông báo chọn gói thứ N và tiếp tục truy tới
T[N1,M-W[N]]. Quá trình này cứ tiếp tục cho đến khi tới hàng 0 của bảng phương
án thì dừng. while (N!=0) {if (T[N][M]!=T[N-1][M] ) { fo < M=M-W[N]; } N--; Chương trình hoàn chỉnh #include #include using namespace std; ifstream fi ("BALO.INP"); // File dau vao ofstream fo("BALO.OUT"); // File dau ra int n,m,w[100],c[100]; long t[100][100]; void nhap() { fi>> n>> m; for (int i=1;i<=n;i++) { fi >> w[i]; 30 fi >>c[i]; } } void qhd() { for (int j=0;j<=m ;j++) t[0][j]=0; for(int i=1;i<=n;i++) for (int j=0;j<=m;j++) if ((j>=w[i])&&(t[i-1][j] t[i][j]=t[i-1][j-w[i]]+c[i]; else t[i][j]=t[i-1][j]; } void truyvet() { fo < while (n!=0) { if (t[n][m]!=t[n-1][m] ) { fo < m=m-w[n]; } n--; } } int main () { nhap(); qhd(); truyvet(); 31 } 2. 3. Hướng dẫn giải một số bài toán bằng quy hoạch động 2.3.1. Bài toán 1. xâu con chung dài nhất Cho xâu s1 và s2. Tìm xâu con chung dài nhất của s1, s2 - Dòng 1: ghi xâu s1 - Dòng 2: ghi xâu s2 * Dữ liệu vào: từ file văn bản XAUCON.INP gồm 2 dòng: * Kết quả: file văn bản XAUCON.OUT gồm 1 dòng: ghi xâu con tìm
được * Ví dụ: XAUCON.INP XAUCON.OUT HOAHONG HAONG THAONGUYEN - Giả sử độ dài của xâu s1, s2 lần lượt là n, m. - Gọi L[i,j] là độ dài xâu con chung dài nhất khi xét xâu s1 gồm i ký tự * Hướng dẫn giải: (bài này ta dựa vào bài tìm dãy con chung dài nhất ở bài toán 2
phần 2.2.2 ở trên) - Công thức truy hồi của bài toán: (i=1,...,n), xâu s2 gồm j ký tự (j=1,...,m). + Khả năng 1: s1[i]=s2[j] thì độ dài của xâu con chung được tăng lên một đơn vị: l[i,j]:=l[i-1,j-1]+1; + Khả năng 2: s1[i] ≠ s2[j] thì độ dài của xâu con chung lớn nhất là:
l[i,j]=max(l[i-1,j],l[i,j-1]). Code để tính L[i,j] for(int i=0;i<=n;i++) L[i,0]=0; // xâu s2 rỗng for(int j=0;j<=m;j++) L[0,j]=0; // xâu s1 rỗng for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) if ( s1[i]=s2[j]) l[i,j]=l[i-1,j-1]+1; 32 else l[i,j]=max(l[i-1,j],l[i,j-1]); * Truy vết tìm ra kết quả: + Để tìm phần tử xâu con ta xuất phát từ ô L[n,m] lùi về ô L[0,0]. Nếu
s1[n]=s2[m] thì ta thêm s1[i] vào dãy con và lùi về ô L[n-1,m-1], còn s1[n] ≠ s2[m]
thì hoặc lùi về ô l[n-1,m] hoặc l[n,m-1]. Nếu l[n,m]=l[n-1,m] thì lùi về ô l[n-1,m] ,
ngược lại lùi về ô l[n,m-1]. Quá trình này được lặp đi lặp lại cho tới khi về đến ô
L[0,0] thì dừng. s:=’’;//khởi tạo xâu rỗng
while ((n!=0)&&(m!=0)) { if (s1[n]=s2[m] ) { s=s+s1[n]; i--;j--; } else if (l[n-1,m]=l[n,m]) i--; else j--; } 2.3.2. Bài toán 2. Cho thuê máy Tại thời điểm 0, Ông chủ cho thuê máy tính nhận được một đơn đặt hàng thuê
sử dụng 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 và ci là các số nguyên và 0<
di< ci <109 ), và sẽ trả tiền sử dụng máy là pi (pi nguyên, 0 * Yêu cầu: Hãy xác định xem ông chủ cần nhận phục vụ những khách hàng
nào, sao cho khoảng thời gian sử dụng máy tính của hai khách hàng được nhận
phục vụ bất kỳ không giao nhau và tổng số tiền thu được từ phục vụ là lớn nhất. - Dòng 1 ghi số n (0< N <1000) - Các dòng tiếp theo, dòng thứ i ghi ba số di, ci, pi cách nhau bởi dấu * Dữ liệu vào: từ file văn bản THUEMAY.INP gồm: cách i=1, 2, 3..., N - Dòng 1 ghi 2 số nguyên theo thứ tự là số lượng khách hàng nhận được * Kết quả: ghi ra file văn bản THUEMAY.OUT gồm 2 dòng: - Dòng 2 ghi chỉ số của khách hàng được phục vụ. 33 phục vụ và tổng tiền thu được. * Ví dụ: THUEMAY.INP THUEMAY.OUT 2 180 3 2 3 150 500 150 1 200 100 400 800 80 - Ta tiến hành sắp xếp tăng dần theo di (thời điểm bắt đầu) và dùng cs[i] để *Hướng dẫn cách giải: - Đặt lính canh d[n+1]= +∞; d[0]= -∞; - Đặt T[i] là tổng tiền thu được mà người i là người đầu tiên trong dãy các lưu lại chỉ số ban đầu khi chưa sắp xếp. - T[0]=0; T[n+1]=0; - Để tính được T[i] ta có công thức truy hồi sau: khách hàng được chọn khi chọn từ người thứ n đến người thứ 0; T[i]=T[jmax]+p[i]; - Lưu vết: để biết khách nào được thuê ta dùng mảng S với S[i] là chỉ số Với T[jmax] là giá trị lớn nhất trong các T[j]; ( j=i+1,...,n+1). Điều kiện để
T[jmax] được chọn là c[i]<=d[jmax]. - Code để tính T[i]: người được chọn ngay sau người thứ i. T[n+1]=0; for(int i=n;i<=0;i--) { jmax:=n+1; for(int j=i+1;j<=n;j++) if (c[i]<=d[j]) if (T[j]>T[jmax]) jmax=j; T[i]=T[jmax]+p[i] ; S[i] =jmax ;// lưu lại các vị trí để biết khách được thuê 34 } 2.3.3. Bài toán 3. Rô bốt ( i,j) Cho một bảng hình chữ nhật kích thước MxN ( M, N nguyên dương và M,
N<=100). M dòng , N cột. mỗi ô được ghi một số nguyên. Rô bốt đi từ một ô nào
đó của cột 1 đến một ô nào đó của cột N. Mỗi bước của Rô bốt được lập trình trước
đi đến một trong các ô theo mũi tên của bảng sau : * Yêu cầu : Hãy tìm cách đi để Rô bốt thu được tổng giá trị các ô là lớn nhất. biết Rô bốt đi qua ô nào thì giá trị của ô đó được cộng vào tổng. - Dòng 1 ghi 2 số M, N - Trong M dòng tiếp theo (dòng thứ i=1...M) ghi N số nguyên không âm, * Dữ liệu vào: từ file ROBOT.INP được mô tả như sau : số thứ j trên mỗi dòng biểu thị cho số ghi ô (i,j) của bảng. - Dòng đầu ghi tổng lớn nhất tìm được - Các dòng sau, mỗi dòng ghi 2 số là ô (i,j) mà Rô Bốt đi qua. * Kết quả: file văn bản ROBOT.OUT như sau : * Ví dụ : ROBOT.INP ROBOT.OUT 6 5 1 8 3 9 4 6 54 7 4 11 6 8 5 1 3 8 10 5 2 0 5 3 2 2 3 1 4 2 5 1 2 6 8 7 9 35 1 6 - Gọi T[i,j] là tổng lớn nhất khi Rô bốt đi từ một ô nào đó của cột 1 đến ô (i,j). để * Hướng dẫn cách giải: đảm bảo tính tổng quát của bài toán ta xây dựng hàng rào cho mảng a và T. T[0,j]=0 ; (j=0,...,n). T[m+1,j]=0 ; (i=0,...,n). T[i,0] :=0 ; ( i=0,...,m). a[i,n+1] :=0 ; (i :=1,...,m) - Khi đó từ ô (i,j) để đi tiếp được đến các ô thì Rô Bốt phải đi đến một trong ba ô a[0,j] :=0 ; (j=0,..., m) - Do yêu cầu của bài nên Rô Bốt sẽ đi đến ô nào có giá trị lớn nhất trong 3 ô trên. sau (i-1,j-1) ; (i,j-1) ; (i+1,j-1). T[i,j]=max (T[i-1,j-1],T[i,j-1],T[i+1,j-1])+a[i,j]; Vậy Max(T[0,N], T[1,N],..., T[M-1,N], T[M,N]) là tổng lớn nhất thõa mãn
bài toán. -Đoạn code để tính T[i,j]: for(int i=1 ;i<=M ;i++) for(int j=1;j<=N;j++) T[i,j]= max (T[i-1,j-1],T[i,j-1],T[i+1,j-1])+a[i,j]; (Bài toán trên có thể áp dụng cho nhiều bài toán tương tự khi ta thay đổi các
hướng mũi tên khác nhau) 2.4. Một số bài toán áp dụng phương pháp quy hoạch động tự giải 2.4.1. Bài 1: Tổng lớn nhất Cho dãy A gồm n số nguyên A1, A2, …, An và số tự nhiên D. Một dãy con của
dãy A là dãy các phần tử liên tiếp từ vị trí L đến vị trí R nào đó trong dãy A và có
độ dài là R-L+1. Yêu cầu: Hãy tìm dãy con độ dài D có tổng các phần tử lớn nhất? * Dữ liệu vào: đọc từ file văn bản MAXSUBD.INP gồm: - Dòng 1 ghi hai số nguyên dương n và D (D ≤ n ≤ 106); - Dòng 2 ghi n số nguyên A1, A2, …, An (|Ai| ≤ 109); Các số trên cùng một dòng cách nhau ít một dấu cách. * Kết quả: ghi ra file văn bản MAXSUBD.OUT giá trị tổng lớn nhất có thể 36 của của dãy con độ dài D trong dãy A. * Ví dụ: MAXSUBD.INP MAXSUBD.OUT 5 2 10 4 2 -8 9 1 * Giới hạn: Có 20/30 test với n ≤ 103, tương ứng 4.0 điểm. Có 10/30 test với n ≤ 109, tương ứng 2.0 điểm. 2.4.2. Bài toán 2: Phân tích Cho dãy A gồm n số nguyên dương A1, A2, …, An (tổng S các phần tử của dãy A không vượt quá 104) và dãy B gồm m số nguyên B1, B2, …, Bm. * Yêu cầu: Hãy đếm xem có bao nhiêu phần tử của dãy B có thể tạo ra từ một hoặc tổng một số phần tử khác nhau của dãy A. * Ví dụ: dãy A(1, 2, 3) và dãy B(4, 8, 6, 6), từ dãy A tạo ra 3 phần tử trong dãy B là: phần tử B1 = 1+3, B3=1+2+3 và B4=1+2+3. * Dữ liệu vào: đọc vào từ file văn bản DEM.INP gồm: - Dòng 1 ghi 2 số nguyên dương n và m; - Dòng 2 ghi n số nguyên dương A1, A2, …, An; - Dòng 3 ghi m số nguyên B1, B2, …, Bm; Các số trên cùng một dòng cách nhau ít một dấu cách. * Kết quả: ghi ra file văn bản DEM.OUT một số duy nhất theo yêu cầu của bài toán. * Ví dụ: DEM.INP DEM.OUT 3 3 4 1 2 3 4 8 6 6 * Giới hạn: - Có 5/15 test với n, m ≤ 15, tương ứng 2.0 điểm; - Có 5/15 test với n ≤ 100, m ≤ 105, tương ứng 1.0 điểm; 37 - Có 5/15 test với n*S ≤ 106, m ≤ 106, tương ứng 1.0 điểm. 2.4.3. Bài toán 3: Bố trí phòng họp Có n cuộc họp, cuộc họp thứ i bắt đầu vào thời điểm ai và kết thúc ở thời
điểm bi, do chỉ có một phòng hội thảo nên hai cuộc họp bất kỳ sẽ được cùng bố trí
phục vụ nếu khoảng thời gian làm việc của chúng chỉ giao nhau tại đầu mút. Yêu
cầu: Hãy bố trí phòng họp để sao cho được nhiều cuộc họp nhất. - Dòng 1:ghi giá trị N - N dòng tiếp theo mỗi dòng ghi thời gian bắt đầu và kết thúc của cuộc * Dữ liệu vào: từ flie PHONGHOP.INP gồm họp - Dòng đầu cho biết số cuộc họp được bố trí - Dòng 2 ghi các cuộc họp được chọn * Kết quả: ra file PHONGHOP.OUT * Ví dụ: PHONGHOP.INP PHONGHOP.OUT 3 5 2 4 3 4 1 3 4 2 3 5 7 2 5 2.4.4. Bài toán 4: Nối điểm Trên hai đường thẳng song song L1 và L2 người ta đánh dấu trên mỗi đường
N điểm. Các điểm trên đường thẳng L1 được đánh số từ 1 đến N từ trái sang
phải, còn các điểm trên đường thẳng L2 được đánh số từ p1, p1,..., pN là một hoán vị của 1, 2,..., N ( hình vẽ dưới đây cho một ví dụ khi 38 N=9). Ta gọi các số gán cho các điểm là số hiệu của chúng. Cho phép nối hai điểm trên hai đường thẳng có cùng số hiệu. Yêu cầu: tìm cách nối được nhiều cặp điểm nhất với điều kiện các đoạn thẳng nối không được cắt nhau - Dòng 1 chứa số nguyên N (N<=1000); - Dòng 2 chứa các số nguyên p1, p1,..., pN cách nhau bởi dấu cách * Dữ liệu vào: từ file WIRE.INP có cấu trúc sau: - Dòng đầu tiên chứa số k là số lượng các đoạn tìm được - Dòng tiếp theo chứa k số hiệu của các đầu mút của các đoạn nối được * Kết quả: ghi ra file WIRE.OUT có cấu trúc sau: ghi theo thứ tự tăng dần. * Ví dụ: WIRE.INP WIRE.OUT 9 5 2 5 3 8 7 4 6 9 1 3 4 6 9 2.4.5. Bài toán 5: Tính tổng của dãy số Cho dãy số nguyên gồm n phần tử a1, a2, …, an (1 n 105) và hai số nguyên
dương p và q (1 p q n). * Yêu cầu: Hãy tính tổng của các phần tử liên tiếp từ ap … aq bằng phương pháp quy hoạch động (lập bảng phương án). * Dữ liệu vào: Ghi trong file văn bản SUM.INP có cấu trúc như sau: - Dòng 1: Ghi số nguyên dương n và k, hai số được ghi cách nhau một dấu cách. - Dòng 2: Ghi n số nguyên a1, a2, …, an, các số được ghi cách nhau ít nhất một dấu cách (-32000 ai 32000). - Dòng thứ i trong k dòng tiếp theo: Mỗi dòng ghi hai số nguyên dương pi và qi, hai số được ghi cách nhau một dấu cách (1 pi qi n). * Dữ liệu ra: Ghi ra file văn bản SUM.OUT theo cấu trúc như sau: - Dữ liệu được ghi trên k dòng: Dòng thứ i ghi một số nguyên là tổng giá trị 39 của các phần tử trong đoạn * Ví dụ: SUM.INP SUM.OUT 21 5 3 6 2 9 -3 5 8 5 1 5 2 3 4 4 2.4.6. Bài toán 6: Dãy Con lớn nhất đan dấu * Dữ liệu vào: từ tệp TANGDAN.INP chứa 1 dãy số nguyên * Yêu cầu: tìm dãy con lớn nhất các phần tử có cùng dấu, (đan dấu). * Dữ liệu ra: ghi vào tệp TANGDAN.OUT gồm 2 dòng - Dòng đầu tiên: ghi độ dài của dãy con lớn nhất - Dòng thứ 2 ghi vị trí bắt đầu của dãy con tìm được * Ví dụ TANGDAN.INP TANGDAN.OUT 1 -2 2 3 4 -1 2 3 1 2 3 4 5 6 8 7 1 -2 -3 -4 -5 6 4 5 6 -7 4 6 2.4.7. Bài toán 7: Sắp xếp xâu Người ta định nghĩa: Từ là một nhóm ký tự đứng liền nhau. Cho một xâu St gồm các ký tự lấy từ tập ‘a’ .. ‘z’ và dấu cách. Xâu không quá 20 từ, mỗi từ dài không quá 10 ký tự. * Yêu cầu: Sắp xếp các từ của xâu ký tự theo thứ tự không giảm của độ dài các từ trong xâu St. * Dữ liệu vào: Cho trong file văn bản SAPXAU.INP, có cấu trúc: - Dòng 1: Ghi một xâu ký tự St (có ít nhất 1 từ). * Dữ liệu ra: Ghi ra file văn bản SAPXAU.OUT, theo cấu trúc: 40 - Dòng 1: Ghi các từ của xâu ký tự sau khi được sắp xếp. Các từ được ghi
cách nhau đúng một dấu cách. * Ví dụ: SAPXAU.INP SAPXAU.OUT acb abcde abcd abc acb abc abcd abcde 2.4.8. Bài toán 8: Tìm mật khẩu Việc bảo vệ máy tính của mình để hạn chế người khác thâm nhập vào là một
vấn đề đặt ra cho mọi nguời sử dụng máy tính. Để tăng tính an toàn trong lưu trữ,
một nguời đã quyết định dấu mật khẩu truy cập máy tính của mình vào một xâu T
với một quy ước sao cho khi cần anh ta có thể lấy lại đuợc mật khẩu từ T như sau: Là một người yêu thích số học anh ta thường chọn mật khẩu P là một số
nguyên tố và đem dấu vào một xâu ký tự T sao cho P chính là số nguyên tố có giá
trị lớn nhất trong số các số nguyên tố tạo được từ các xâu con của T (xâu con của
một xâu ký tự T là một chuỗi liên tiếp các ký tự trong T). Ví dụ: xâu T= “timpassword232432fsdgd45435dsfdsf” chứa mật khẩu là 43 vì T
chứa các xâu con ứng với các số nguyên tố 2, 3, 23, 43, và 5. Yêu cầu: Cho một xâu ký tự T chiều dài không quá 250 ký tự. Tìm mật khẩu P đã
dấu trong xâu T biết P có giá trị nhỏ hơn 105. Dữ liệu cho đảm bảo T chứa ít nhất
1 số nguyên tố. * Dữ liệu: Vào từ file văn bản PASSWORD.INP gồm 1 dòng duy nhất là xâu T. * Kết quả: Ghi ra file văn bản PASSWORD.OUT chứa số P tìm được. * Ví dụ: PASSWORD.INP PASSWORD.OUT timpassword232432fsdgd45435dsfdsf 43 2.4.9. Bài toán 9: TWOVALS Cho dãy số nguyên . Tìm độ dài đoạn con dài nhất của dãy chỉ bao gồm hai giá trị. * Dữ liệu: Vào từ file văn bản TWOVALS.INP − Dòng : số nguyên ; − Dòng : số nguyên . * Kết quả: Ghi ra file văn bản TWOVALS.OUT một số nguyên duy nhất là độ dài đoạn con dài nhất chỉ bao gồm hai giá trị theo phương án tìm được. Các số trên một dòng của input file được ghi cách nhau bởi ít nhất một dấu 41 cách * Ví dụ TWOVALS.INP TWOVALS.OUT 7 4 1 3 2 3 3 1 2 2.5. So sánh kết quả trước và sau khi áp dụng phương pháp Quy hoạch động
vào việc bồi dưỡng 2.5.1. Trước khi áp dụng phương pháp Quy hoạch động vào việc bồi dưỡng
học sinh giỏi - Trước khi chưa đưa phương pháp Quy hoạch động vào việc bồi dưỡng học
sinh giỏi, thì khi gặp những bài toán phức tạp học sinh thường sử dụng những
phương pháp cơ bản thông thường để cài đặt chương trình, dẫn đến một trong hai
vấn đề. Một là hiểu đề nhưng không cài đặt được chương trình dẫn đến mất điểm
hoàn toàn câu đó. Hai là có cài đặt được chương trình nhưng không đảm bảo về
mặt thời gian, hoặc là kết quả sai đáp án, dẫn đến mất rất nhiều test, cho nên đạt
điểm không cao. 42 Dưới đây là một trong số các hình ảnh ví dụ minh hoạ khi làm bài trước khi
chưa áp dụng biện pháp. Lỗi mất test do thuật toán chưa tối ưu hoặc chưa đúng dẫn
đến chương trình chạy quá thời gian. Và kết quả khác đáp án với bộ test của bài Dưới đây là bảng thống kê chi tiết về số điểm trên từng câu. Cũng như lỗi mất
test trên mỗi câu. Lỗi mất test ở đây chủ yếu là do thuật toán chưa tối ưu, đang sử
dụng những thuật toán cơ bản thông thường, mà chưa biết cách sử dụng phương
pháp Quy hoạch động vào để cài đặt chương trình. Dẫn đến mất test do chương
trình chạy quá thời gian, hoặc là kết quả khác với đáp án Tên HS Câu 1(5đ) Câu 2(6đ) Câu 3(4đ) Câu 4(5đ) Tổng Điểm(20đ) Cường 5.0 2.4 3.0 1.4 11.8 Lỗi Hết test Mất 9 test Mất 2 test Mất 36 test Huy 2.5 2.4 1.0 0 5.9 Lỗi Mất 5 test Mất 9 test Mất 6 test Mất 50 test 2.5.2. Sau khi áp dụng phương pháp Quy hoạch động vào việc bồi dưỡng học
sinh giỏi - Sau khi áp dụng phương pháp Quy hoạch động vào việc bồi dưỡng học sinh
giỏi, tôi nhận thấy tư duy và kỹ năng của các em đã tiến bộ lên rất nhiều. Khi gặp
các bài toán phức tạp trước đây, các em đã biết phân tích và cài đặt chương trình
để giải quyết vấn đề rất tốt. Đặc biệt là các dạng bài toán có thể dùng phương pháp
Quy hoạch động để xử lý. Các em không còn lúng túng mà rất tự tin. Qua đó đạt
kết quả cao. - Dưới đây là một trong các hình ảnh minh hoạ bằng chương trình chấm
Themiss sau khi áp dụng phương pháp Quy hoạch động vào việc bồi dưỡng. Từ kết
quả ban đầu điểm rất thấp. Sau khi học sinh nghiên cứu và áp dụng vào cài đặt
chương trình thì đã khắc phục được các lỗi trước đó. 43 - Từ việc mất test do lỗi quá thời gian và kết quả khác đáp án. Thì nay đã ăn
hết test và điểm cao hơn nhiều. Qua đó khi học sinh gặp những bài toán dạng này
thì học sinh rất tự tin để xử lý và ăn hết điểm Bảng điểm chi tiết từng câu Tên HS Câu 1(5đ) Câu 2(6đ) Câu 3(4đ) Câu 4(5đ) Tổng Điểm(20đ) Cường 5.0 2.4 3.0 1.4 20 Lỗi Hết test Hết test Hết test Hết test Huy 5.0 6.0 4.0 5.0 20 Lỗi Hết test Hết test Hết test Hết test Tất cả các câu thì học sinh đã xử lý và cài đặt thuật toán một cách tối ưu nhất (ăn hết test) . Bằng cách sử dụng phương pháp Quy hoạch động vào để cài đặt
chương trình. 44 Từ đó học sinh không những nâng cao khả năng tư duy mà còn rất tự tin khi
gặp những dạng bài mà có thể sử dụng phương pháp Quy hoạch động vào để giải
quyết vấn đề một cách triệt để. Phần III. Kết luận: 1. Kết Luận 1.1 Với mục tiêu đặt ra đề tài đã làm được: Trình bày rõ lí thuyết về quy hoạch động, cách nhận dạng các bài toán có thể xử lí được bằng phương pháp quy hoạch động và một số thao tác xử lí cơ bản. Qua quá trình tìm hiểu về đề tài quy hoạch động tôi nhận thấy một bài toán
quy hoạch động có thể có nhiều cách tiếp cận khác nhau, chọn cách nào là tùy theo
yêu cầu bài toán sao cho dễ dàng cài đặt nhất. Phương án này thường không khó
khăn trong bảng phương án, không khó khăn trong việc tìm cơ sở quy hoạch động,
mà khó khăn chính là nhìn nhận ra bài toán quy hoạch động và tìm ra công thức
truy hồi giải nó, công việc này không phải đòi hỏi sự nhanh nhạy, khôn khéo, mà
chỉ từ sự rèn luyện mới có thể có được. Phân tích đánh giá qua một số bài toán cụ thể để thấy được các bài toán áp
dụng phương pháp xử lí quy hoạch động hoặc kết hợp phương pháp khác với
phương pháp xử lí quy hoạch động sẽ mang lại một hiệu quả cao trong giải các bài
toán về cả mặt thời gian và yêu cầu bộ nhớ. Đề tài này được áp dụng vào việc bồi dưỡng học sinh giỏi. Đóng góp vào kết quả vào cuộc thi học sinh giỏi tỉnh Nghệ An môn Tin Học như sau: Năm học 2021-2022 Tôi đã bồi dưỡng 2 Em tham gia kỳ thi học sinh giỏi cấp Tỉnh và đạt kết quả như sau: Em Hoàng Trọng Huy trường THPT Con Cuông, đạt giải ba với số điểm 16,2 điểm Em Văn Đức Cường trường THPT Con Cuông, đạt giải nhì với số điểm 18 điểm Năm học 2022-2023 Năm học này tôi không phụ trách bồi dưỡng học sinh giỏi tỉnh. Năm nay Tôi
đã bồi dưỡng 2 Em tham gia kỳ thi học sinh giỏi cấp Trường và đạt kết quả như
sau: Em Doãn Thị Phương Hoa đạt giải khuyến khích với số điểm 11,8 điểm Em Ngô Xuân Hoàng đạt giải nhất với số điểm 16,8 điểm 1.2. Hướng phát triển của đề tài: Tìm thêm nhiều bài tập có thể áp dụng các phương pháp kết hợp xử lí bằng
phương pháp quy hoạch động hiệu quả và phân dạng để áp dụng một cách hiệu quả
trong công tác bồi dưỡng đội tuyển học sinh giỏi. 45 Hiện tại đề tài đã áp dụng vào việc bồi dưỡng học sinh giỏi ở các trường
THPT cũng như THCS thuộc huyện Con Cuông và đã gửi đi các trường khác để phục vụ khảo sát tính cấp thiết cũng như tính khả thi của đề tài. Đề tài cũng đã
nhận được các phản hồi tích cực của các thầy cô cũng như các em học sinh. Trong những năm sau đề tài sẽ áp dụng vào nhiều trường hơn nữa nhằm nâng
cao chất lượng cũng như đạt thành tích cao hơn nữa trong các cuộc thi học sinh
giỏi, olimpic tin học trẻ, thi vào lớp chuyên tin trường Phan Bội Châu, trường
Chuyên Bộ do tỉnh Nghệ An tổ chức hàng năm. Đề tài được hoàn thành ngoài sự nổ lực cố gắng của bản thân còn có sự giúp
đỡ nhiệt tình của các đồng nghiệp. Tuy nhiên do điều kiện thời gian cũng như kinh
nghiệm bồi dưỡng còn chưa nhiều nên nội dung có thể còn gặp nhiều thiếu sót. Rất
mong nhận được nhiều sự đóng góp ý kiến của quý thầy cô, bạn bè đồng nghiệp,
để đề tài có thể hoàn thiện hơn và áp dụng vào giảng dạy bồi dưỡng học sinh giỏi
một cách hiệu quả. 2. Một số kiến nghị đề xuất Để áp dụng đề tài hiệu quả trong quá trình bồi dưỡng giáo viên cần bồi dưỡng
nhiều hơn nữa về lí thuyết Quy hoạch động. Xem và làm các bài toán quy hoạch
động từ cơ bản, điển hình cho đến nâng cao. Một số thao tác xử lí bằng phương
pháp quy hoạch động và các phương pháp khác để ứng dụng phương pháp này
cũng như kết hợp các phương pháp với phương pháp này một cách hiệu quả nhất. 46 Hướng dẫn, khuyến khích học sinh tham gia giải bài, tìm kiếm các bài tập có
phân dạng về xử lí bằng phương pháp quy hoạch đông trên các trang mạng giải bài
trực tuyến (đặc biệt trên trang vn.spoj.com, laptrinhphothong.vn, chuyentin.pro…)
và các đề thi học sinh giỏi qua các năm. 1. Cấu trúc dữ liệu của Lê Minh Hoàng 2. Hồ Sĩ Đàm_Tài liệu giáo khoa chuyên tin quyển 1 3. Hồ Sĩ Đàm _Sách giáo khoa Tin học 11 4. Lê Minh Hoàng_ Chuyên đề tin 5. Toán rời rạc của Nguyễn Đức Nghĩa, Nguyễn Tô Thành 6. Các chuyên đề 7. Các trang web : - TÀI LIỆU THAM KHẢO - http://vnoi.info/ - http://www.topcode.com - http://cm.baylor.edu/welcome - http://vn.spoj.com - http://laptrinhphothong.vn 47 http://chuyentin.pro PHỤ LỤC KHẢO SÁT SỰ CẤP THIẾT VÀ TÍNH KHẢ THI CỦA CÁC GIẢI PHÁP
ĐỀ XUẤT 1. Mục đích khảo sát - Khảo sát sự cấp thiết và tính khả thi của các giải pháp được đề xuất trong đề tài. Từ đó xây dựng đề tài tốt hơn và phù hợp hơn với thực trạng hiện nay. 2. Nội dung và phương pháp khảo sát 2.1. Nội dung khảo sát 1. Các giải pháp được đề xuất có thực sự cấp thiết với vấn đề nghiên cứu hiện nay không - Cho học sinh và giáo viên giảng dạy môn Tin học ở các trường khác nhau
đánh giá khách quan về sự cấp thiết với các giải pháp được đề xuất trong thời kì
hiện nay 2. Các giải pháp được đề xuất có khả thi đối với vấn đề nghiên cứu hiện nay không - Cho học sinh và giáo viên giảng dạy môn Tin học ở các trường khác nhau
đánh giá khách quan tính khả thi với các giải pháp được đề xuất trong thời kì hiện
nay 2.2. Phương pháp khảo sát và thang đánh giá - Gửi đề tài sáng kiến, các biện pháp đề xuất cho hai đối tượng là học sinh và giáo viên dạy môn Tin học ở các trường trong và ngoài địa bàn khác nhau để
nghiên cứu và đánh giá khách quan các giải pháp thông qua biểu mẫu google form. - Thang đánh giá có 4 mức để lựa chọn, trên 2 yếu tố là tính khả thi và tính cấp thiết của các giải pháp để học sinh và giáo viên đánh giá một cách minh bạch
và công khai theo đúng mẫu quy định. - Sử dụng biểu mẫu google form thống kê và phân tích một cách tự động và khách quan 3. Đối tượng khảo sát Tổng hợp các đối tượng khảo sát TT Đối tượng Số lượng 1 Giáo viên 18 2 Học sinh 50 48 Tổng 68 4. Kết quả khảo sát về sự cấp thiết và tính khả thi của các giải pháp đã đề xuất 4.1. Sự cấp thiết của các giải pháp đã đề xuất Đánh giá sự cấp thiết của các giải pháp đã đề xuất Các thông số Các giải pháp TT X Mức 44.1% - Rất cấp thiết 1 55.9% - Cấp thiết Sử dụng phương pháp Quy
hoạch động vào việc ôn luyện và
lập trình bồi dưỡng học sinh giỏi 0% - Ít cấp thiết 0% - Không cấp thiết Thống kê đánh giá tính cấp thiết của biện pháp trên biểu mẫu Google form Từ số liệu thu được ở bảng trên có thể rút ra những nhận xét 49 - Giải pháp đề xuất được học sinh và giáo viên đánh giá cao về sự cấp thiết.
Từ đó đề tài phù hợp và có tính cấp thiết với học sinh và giáo viên giảng dạy môn
Tin học hiện nay 4.2. Tính khả thi của các giải pháp đã đề xuất Đánh giá tính khả thi của các giải pháp đã đề xuất Các thông số TT Các giải pháp X Mức 1 48.5% - Rất khả thi 6.2% - Khả thi Sử dụng phương pháp Quy
hoạch động vào việc ôn luyện và
lập trình bồi dưỡng học sinh giỏi 0% - Ít khả thi 0% - Không khả thi Thống kê đánh giá tính khả thi của biện pháp trên biểu mẫu Google form Từ số liệu thu được ở bảng trên có thể rút ra những nhận xét - Giải pháp đề xuất được học sinh và giáo viên đánh giá cao về tính khả thi.
Từ đó đề tài phù hợp và có tính khả thi với học sinh và giáo viên giảng dạy môn
Tin học hiện nay Link khảo sát: https://docs.google.com/forms/d/1J6IMSbMVQD3Ep3nDUA- mzL11cc0AyKe4U6MVBlAJf1k/edit#responses Link code các bài toán và mô phỏng cũng như hướng dẫn các bài toán trong đề tài bằng ngôn ngữ lập trình Pascal: https://docs.google.com/document/d/1__t8mM9fxtnJD2CZ- 50 xqyZprXTy2XizqG/edit?usp=sharing&ouid=116870540632546263626&rtpof=tru
e&sd=true* Độ phức tạp của thuật toán: Với đoạn code trên thì dễ thấy chi phí không
gian cài đặt trên là O(nm), chi phí thời gian là O(nm). Với n là số gói kẹo của dãy
a, s là số kẹo ở phần ít.
* Truy vết tìm kết quả: Tính được bảng phương án ta biết ngay được giá trị
của T[n,s] và đây chính là giá trị lớn nhất khi chọn các i gói trong số n gói với giới
hạn tổng s. Sử dụng mảng kt[i] để đánh dấu các gói ở các phần, ta khởi tạo chúng
bằng 0. Sau đó nếu T[n,s]=T[n-1,s] thì tức là không chọn gói thứ n, ta lại truy tiếp
đến gói T[n-1,s]. Còn nếu T[n,s] ≠ T[n-1,s] tức chọn gói thứ n nên kt[n]=1 và tiếp
tục truy tới T[n-1,na[n]]. Quá trình này cứ tiếp tục cho đến khi tới hàng 0 của bảng
phương án thì dừng. Sau đó nếu kt[i]=1 thì thuộc phần 1 còn bằng 0 thì thuộc phần
