SKKN Giúp học sinh tiếp cận với phương pháp quy hoạch động bằng một số bài toán đơn giản trong Tin học

 MỤC LỤC
CÁC KÝ HIỆU VIẾT TẮT TRONG SÁNG KIẾN KINH NGHIỆM ..........................3
I. Lời giới thiệu ..............................................................................................................4
II. Tên sáng kiến:............................................................................................................5
III. Tác giả sáng kiến:.....................................................................................................5
IV. Chủ đầu tư tạo ra sáng kiến: ....................................................................................5
V. Lĩnh vực áp dụng sáng kiến: .....................................................................................5
VI. Ngày sáng kiến được áp dụng lần đầu hoặc áp dụng thử: .......................................5
VII. Mô tả bản chất của sáng kiến: ................................................................................5
 PHẦN I: SƠ ĐỒ NỘI DUNG SÁNG KIẾN KINH NGHIỆM ................................6
 PHẦN II: NỘI DUNG SÁNG KIẾN KINH NGHIỆM.............................................7
 I. Một số khái niệm cơ bản về phương pháp quy hoạch động ...............................7
 1.1. Khái niệm....................................................................................................7
 1.2. Các bước giải quyết bài toán bằng phương pháp quy hoạch động. ............7
 II. So sánh phương pháp quy hoạch động với các phương pháp khác.................11
 2.1. Phương pháp quy hoạch động và phương pháp đệ quy ............................11
 2.2. Phương pháp quy hoạch động và phương pháp vét cạn............................15
 III. Cài đặt chương trình cho một số bài toán đơn giản thường gặp ....................15
 Ví dụ 1: Bài toán tính an (n là số nguyên dương). ...........................................16
 Ví dụ 2: Tính n! (n là số nguyên dương)..........................................................18
 Ví dụ 3: Dãy số fibonacci: ...............................................................................20
 Ví dụ 4: Bài toán tháp Hà Nội..........................................................................22
 Ví dụ 5: Bài toán cái túi ...................................................................................24
 IV. Bài tập tự giải.................................................................................................29
 Bài toán 1: Dãy con có tổng bằng S................................................................29
 Bài toán 2: Dãy con có tổng lớn nhất...............................................................29
 Bài toán 3: Chia kẹo.........................................................................................30
VIII. Những thông tin cần bảo mật: Không .................................................................30
 1 CÁC KÝ HIỆU VIẾT TẮT TRONG SÁNG KIẾN KINH NGHIỆM
 Ký hiệu Ý nghĩa
SKKN Sáng kiến kinh nghiệm
THPT Trung học phổ thông
ĐQ Đệ quy
DQ Đệ quy
QHĐ Quy hoạch động
QHD Quy hoạch động
PP Phương pháp
NXB Nhà xuất bản
 3 gian thực hiện càng nhanh, chiếm ít bộ nhớ hơn sẽ được đánh giá cao hơn. Và trong 
những trường hợp như vậy, quy hoạch động là một trong những thuật toán phù hợp. 
Chỉ cần làm được những bài này là học sinh gần như có giải. Tuy nhiên, các em thường 
hay bị nhầm lẫn và khó phân biệt được khi thuật toán sử dụng phương pháp quy hoạch 
động và các phương pháp khác. Nên việc làm cho các em học sinh phổ thông có thể 
phân biệt và thấy được sự ưu việt của quy hoạch động từ đó sử dụng thành thạo phương 
pháp này trong lập trình không phải là vấn đề dễ dàng. Hiểu rõ các thuật toán là bước 
đầu giúp các em học sinh tự tin đồng thời phân tích bài toán và xác định phương pháp 
giải đúng đắn sẽ giúp các em có thành tích tốt hơn. Là một giáo viên giảng dạy bộ môn 
Tin học ở trường trung học phổ thông, sau nhiều năm tham gia dạy bồi dưỡng đội tuyển 
thi học sinh giỏi, tôi nhận thấy việc bồi dưỡng học sinh giỏi là nhiệm vụ vô cùng quan 
trọng và việc ứng dụng phương pháp quy hoạch động trong thiết kế thuật toán là một 
mảng kiến thức rất cần thiết đối với học sinh tham gia đội tuyển học sinh giỏi môn Tin 
học. 
 Vì vậy tôi chọn đề tài “Giúp học sinh tiếp cận với phương pháp quy hoạch động 
bằng một số bài toán đơn giản trong Tin học” làm đề tài nghiên cứu. Hy vọng đây sẽ 
là một tư liệu hữu ích cho các giáo viên, học sinh và những người quan tâm đến phần 
kiến thức này. 
II. Tên sáng kiến: 
 Giúp học sinh tiếp cận với phương pháp quy hoạch động bằng một số bài toán 
đơn giản trong Tin học.
III. Tác giả sáng kiến:
 - Họ và tên: Nguyễn Thị Hà
 - Địa chỉ tác giả sáng kiến: Xã Đại Đồng – huyện Vĩnh Tường – tỉnh Vĩnh Phúc
 - Số điện thoại: 0977 212 636
 - E_mail: nguyenthiha.gvnguyenvietxuan@vinhphuc.edu.vn
IV. Chủ đầu tư tạo ra sáng kiến: Nguyễn Thị Hà
V. Lĩnh vực áp dụng sáng kiến: Dạy bồi dưỡng học sinh đội tuyển Tin học, giáo viên 
hoặc những người quan tâm tới lập trình.
VI. Ngày sáng kiến được áp dụng lần đầu hoặc áp dụng thử: Năm 2017 – 2018.
VII. Mô tả bản chất của sáng kiến:
 5 PHẦN II: NỘI DUNG SÁNG KIẾN KINH NGHIỆM
I. Một số khái niệm cơ bản về phương pháp quy hoạch động
1.1. Khái niệm
* Quy hoạch động (Dynamic Programming) là một phương pháp rất hiệu quả giải nhiều 
bài toán tin học, đặc biệt là những bài toán tối ưu.
* Quy hoạch động trong ngành khoa học máy tính: Là một phương pháp giảm thời 
gian chạy của các thuật toán thể hiện các tính chất của các bài toán con gối nhau 
(Overlapping subproblem) và cấu trúc con tối ưu (Optimal substructure). 
 Phương pháp 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 những bài toán lớn hơn cho tới khi giải 
được bài toán lớn nhất (bài toán ban đầu). Ý tưởng cơ bản của phương pháp quy hoạch 
động là tránh tính toán lại các bài toán con đã xét, 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 độ.
* Một bài toán P muốn giải bằng phương pháp quy hoạch động cần có 2 đặc điểm 
sau:
 - Bài toán P thỏa mãn nguyên lý tối ưu Bellman, nghĩa là có thể sử dụng lời giải 
tối ưu của các bài toán con từ mức thấp nhất để tìm dần lời giải tối ưu cho bài toán con 
ở mức cao hơn và cuối cùng là lời giải tối ưu cho bài toán P.
 - Bài toán P có các bài toán con phủ chồng lên nhau, nghĩa là không gian bài toán 
con “hẹp” không tạo dạng hình cây.
1.2. Các bước giải quyết bài toán bằng phương pháp quy hoạch động.
- Bước 1: Xây dựng hàm mục tiêu
 Áp dụng nguyên lý tối ưu của Bellman ta phân rã bài toán ban đầu thành các bài 
toán con có cùng cấu trúc sao cho việc giải quyết bài toán con cấp i phụ thuộc vào kết 
quả của các bài toán con trước đó. Cụ thể hóa bước này là ta phải xây dựng được hàm 
mục tiêu F(i) là nghiệm của bài toán con cấp i.
- Bước 2: Xác định các bài toán cơ sở.
 Bài toán cơ sở là các bài toán con nhỏ nhất mà ta có thể biết ngay kết quả hoặc 
tính được kết quả dễ dàng. Đây chính là cơ sở để tính nghiệm cho các bài toán cấp lớn 
hơn.
- Bước 3: Xây dựng công thức truy hồi
 7 - Bước 4: Bảng phương án
 i 1 2 3 4 5 6 7 .. .
 f(i) 1 1 2 3 5 8 13
- Bước 5: Nghiệm f(n) của bài toán
Bài toán 4: Tháp Hà Nội
Chuyển n chiếc đĩa từ cọc 1 sang cọc 2 theo thứ tự từ lớn đến nhỏ. có sử dụng cọc 
3 làm cọc trung gian. Mỗi lần di chuyển được 1 đĩa. Và đĩa đĩa lớn phải ở dưới đĩa 
nhỏ.
- Bước 1: Hàm mục tiêu: f(i)
- Bước 2: Các bài toán cơ sở: f(1): = 1
- Bước 3: Công thức truy hồi: f(i):=2*f(i-1)+1
- Bước 4: Bảng phương án
 i 1 2 3 4 5 .. .
 f(i) 1 3 7 15 31
- Bước 5: Nghiệm f(n) của bài toán
Bài toán 5: Bài toán cái túi
 Trong siêu thị có n gói hàng (n <= 100), gói hàng thứ i có trọng lượng là Wi 
<= 100 và trị giá Vi <= 100. Một tên trộm đột nhập vào siêu thị, sức của tên trộm 
không thể mang được trọng lượng vượt quá M (M <= 100). Hỏi tên trộm sẽ lấy đi 
những gói hàng nào để được tổng giá trị lớn nhất.
- Bước 1: Hàm mục tiêu: F[i,j] = max(F[i-1,j],V[i]+ F[i,j-W[i]])
- Bước 2: Các bài toán cơ sở: F[0,j] = 0
- Bước: Công thức truy hồi tính B[i, j]. 
 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: 
 + 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] 
 + 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à Wi  j) thì 
F[i, j] bằng giá trị gói thứ i là Vi 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 - Wi. Tức là về mặt giá trị thu 
được: F[i, j] = Vi + F[i - 1, j - Wi] Vì theo cách xây dựng F[i, j] là giá trị lớn nhất có thể 
nên nó sẽ là max trong 2 giá trị thu được ở trên. 
 9 Nếu f[n,M]=f[n-1,M] thì tức là không chọn vật thứ n, ta truy về f[n-1,M]. Còn nếu 
f[n,M]≠f[n-1,M] thì ta thông báo rằng phép chọn tối ưu có chọn vật thứ n và truy về 
f[n-1,M-Wn].
* Trường hợp 2: Trong bảng phương án F[n,m] chính là giá trị lớn nhất thu được khi 
chọn trong cả n vật với giới hạn trọng lượng là M.
Nếu f[n,M] = f[n-1,M] thì tức là không chọn vật thứ n, ta truy về f[n-1,M]. Còn nếu 
f[n,M] ≠ f[n-1,M] thì ta thông báo rằng phép chọn tối ưu có chọn vật thứ n và truy về 
f[n,M-Wn].
II. So sánh phương pháp quy hoạch động với các phương pháp khác
2.1. Phương pháp quy hoạch động và phương pháp đệ quy
 Về mặt nguyên tắc phương pháp quy hoạch động rất giống với phương pháp đệ 
quy. 
* Giống nhau: Cả hai phương pháp đều sử dụng lời giải của các bài toán có kích thước 
bé hơn, đồng dạng với bài toán ban đầu để đưa ra lời giải của bài toán ban đầu. 
* Khác nhau: 
 Quy hoạch động Đệ quy
 - Gọi thực hiện các bài toán cả hai chiều: - Gọi thực hiện các bài toán có kích 
 Từ trên xuống (top - down) hoặc từ dưới thước lớn trước rồi đến các bài toán có 
 lên (bottom - up). kích thước bé hay thực hiện các bài 
 toán từ trên xuống (top - down)
 - Các kết quả trung gian được lưu lại, khi - Các kết quả trung gian không được 
 giải các bài toán lớn hơn chỉ cần cần lấy ra lưu lại nên khi cần dùng đến phải tính 
 không cần tính toán lại. đi tính lại nhiều lần.
 - Dành phần lớn bộ nhớ để lưu trữ các kết - Dùng phần lớn bộ nhớ để lưu trữ 
 quả trung gian. chương trình con.
 - Tốn ít bộ nhớ hơn và thời gian thực hiện - Chiếm dung lượng bộ nhớ rất lớn, 
 nhanh hơn thông thường độ phức tạp là hàm mũ.
 Trong hầu hết các bài toán thì quy hoạch động chiếm ưu thế hơn đệ quy nhưng 
trong một vài trường hợp cả hai bài toán thực hiện đều như nhau. Ta xét một số ví dụ 
cả về quy hoạch động và đệ quy để thấy được tính ưu việt của quy hoạch động.
 Ví dụ 1: Bài toán tính an (n là số nguyên dương)
 Quy hoạch động Đệ quy
 11