Một số bài toán quy hoạch động tiêu biểu - Trường THPT Chuyên Võ Nguyên Giáp

 Trường THPT Chuyên Võ Nguyên Giáp
 MỘT SỐ BÀI TOÁN QHD TIÊU BIỂU
1. Khái niệm về phương pháp quy hoạch động:
 Phương pháp quy hoạch động dùng để giải bài toán tối ưu có bản chất đệ 
quy, tức là việc tìm phương án tối ưu cho bài toán đó có thể đưa về tìm phương án 
tối ưu của một số hữu hạn các bài toán con. 
 Ðối với một số bài toán đệ quy, nguyên lý chia để trị (divide and conquer) 
thường đóng vai trò chủ đạo trong việc thiết kế thuật toán. Ðể giải quyết một bài 
toán lớn, ta chia nó thành nhiều bài toán con cùng dạng với nó để có thể giải quyết 
độc lập. 
 Trong phương án quy hoạch động, nguyên lý chia để trị càng được thể hiện 
rõ: Khi không biết phải giải quyết những bài toán con nào, ta sẽ đi giải quyết toàn 
bộ các bài toán con và lưu trữ những lời giải hay đáp số của chúng với mục đích sử 
dụng lại theo một sự phối hợp nào đó để giải quyết những bài toán tổng quát hơn.
 Ðó chính là điểm khác nhau giữa Quy hoạch động và phép phân giải đệ quy 
và cũng là nội dung phương pháp quy hoạch động:
 - Phép phân giải đệ quy bắt đầu từ bài toán lớn phân ra thành nhiều bài toán 
con và đi giải từng bài toán con đó. Việc giải từng bài toán con lại đưa về phép 
phân ra tiếp thành nhiều bài toán nhỏ hơn và lại đi giải các bài toán nhỏ hơn đó bất 
kể nó đã được giải hay chưa.
 - 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).
 Bài toán giải theo phương pháp quy hoạch động gọi là bài toán quy hoạch 
động. 
 Công thức phối hợp nghiệm của các bài toán con để có nghiệm của bài toán 
lớn gọi là công thức truy hồi của quy hoạch động.
 Tập các bài toán có ngay lời giải để từ đó giải quyết các bài toán lớn hơn gọi 
là cơ sở quy hoạch động.
 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 gọi 
là bảng phương án của quy hoạch động. 
 Trước khi áp dụng phương pháp quy hoạch động ta phải xét xem phương 
pháp đó có thỏa mãn những yêu cầu dưới đây không:
Gi¸o viªn: TrÇn L­¬ng V­¬ng Trang 1 Trường THPT Chuyên Võ Nguyên Giáp
3. Ví dụ về các bài toán có thể giải bằng phương pháp quy hoạch động
3.1. Bài toán Tính N! GT.PAS
 1 n 0
 Ta có định nghĩa như sau: n! = nếu 
 n*(n 1)! n 0
 Cho một số nguyên dương n (0 n 13). 
Yêu cầu: Hãy tính n! 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 GT.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương n.
Dữ liệu ra: Ghi ra file văn bản GT.OUT theo cấu trúc như sau:
- Dòng 1: Ghi giá trị tính được của n!
Ví dụ:
 GT.INP GT.OUT
 3 6
Thuật toán:
 Gọi GT[i] là giá trị của i! (0 i 13)
 Ta có công thức quy hoạch động như sau: 
 GT[i] := GT[i-1]*i;
 Như vậy, việc tính n! sẽ được thực hiện bằng vòng lặp:
 GT[0] :=1;
 For i:=1 to n do
 GT[i] := GT[i-1]*i;
 Kết quả: giá trị của n! nằm trong phần tử GT[n].
3.2. Bài toán Tính dãy Fibonaci FIBO.PAS
 1 n 0 or n 1
 Ta có định nghĩa như sau: F(n) = nếu 
 F(n 1) F(n 2) n 1
 Cho một số nguyên dương n (0 n 50). 
Yêu cầu: Hãy tính F(n) 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 FIBO.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương n.
Dữ liệu ra: Ghi ra file văn bản FIBO.OUT theo cấu trúc như sau:
- Dòng 1: Ghi giá trị tính được của F(n).
Ví dụ:
Gi¸o viªn: TrÇn L­¬ng V­¬ng Trang 3 Trường THPT Chuyên Võ Nguyên Giáp
Thuật toán:
 Gọi A[i] là giá trị của phần tử thứ i trong dãy số a1, a2, , an.
 Gọi T[i] là tổng giá trị các phần tử a1, a2, , ai (1 i n).
 Ta có công thức quy hoạch động để tính T[i] như sau:
 T[i] := T[i - 1] + A[i];
 Như vậy, việc tính T[n] được thực hiện bằng vòng lặp:
 T[0] := 0;
 For i:=1 to n do
 T[i] := T[i - 1] + A[i];
 Kết quả: Tổng các phần tử liên tiếp từ ap đến aq được tính theo công thức:
 Sum := A[q] - A[p-1];
3.4. TRIANGLE PASCAL (Tam giác Pascal) TRIANPAS.PAS
 Tam giác Pascal là một mô hình 1
dùng để đưa ra các hệ số của khai triển nhị 1 7 1
thức Newton bậc N (x+1)N. 1 2 1
Ví dụ: trong khai triển (x+1) 2 = x2 + 2x +1 1 3 3 1
có các hệ số là 1 2 1 1 4 6 4 1
 1 10 10
Trong khai triển (x+1)3 = x3 + 3x2 + 3x + 1 5 5 1
có các hệ số là 1 3 3 1
Yêu cầu: Hãy tìm các hệ số trong khai triển nhị thức Newton (x + 1)N.
Dữ liệu vào: Cho trong file văn bản TRIANPAS.INP có cấu trúc như sau:
Dòng 1: Ghi số nguyên dương N (1 ≤ N ≤ 100).
Dữ liệu ra: Ghi ra file văn bản TRIANNUM.OUT theo cấu trúc:
Dòng 1: Ghi ra các số nguyên dương lần lượt là các hệ số trong khai triển nhị thức 
Newton (x + 1)N, các số được ghi cách nhau một dấu cách.
Ví dụ: 
 TRIANPAS.INP TRIANPAS.OUT
 5 1 5 10 10 5 1
Thuật toán:
 + Ta xây dựng mảng hai chiều có kích thước [0..100, 0..101]
Gi¸o viªn: TrÇn L­¬ng V­¬ng Trang 5 Trường THPT Chuyên Võ Nguyên Giáp
 TRIANNUM.INP TRIANNUM.OUT
 6 48
 7
 2 8
 5 9 3
 4 6 9 2
 7 8 5 6 6
 1 3 4 9 8 1
Thuật toán:
 + Ta xây dựng mảng hai chiều có kích thước [1..100, 0..101]
 + Sử dụng phương pháp quy hoạch động với công thức như sau:
 Dòng thứ i được tính thông qua dòng i-1
 L[i, j] = Max(L[i-1, j-1] + L[i-1, j]) + A[i, j]
 + Thuật toán cụ thể như sau:
 L[1, 1] = A[1, 1];
 For i:= 2 to N do
 Begin
 For j:=1 to i do
 L[i, j] = Max(L[i-1, j-1] + L[i-1, j]) + A[i, j];
 End;
 + Kết quả được lưu trữ ở dòng N, cụ thể:
 Tong: = L[N, 1]
 For j:= 2 to N do
 if (L[N, j] > Tong) then
 Tong := L[N, j];
4. Các bài tập nâng cao áp dụng phương pháp quy hoạch động để giải
4.1. Bài toán Cử tạ DUMBBELL.??? 
 Rèn luyện thể lực bằng cách tập nâng tạ thu 
hút được sự chú ý của rất nhiều bạn trẻ. Tạ là một 
thanh trục có gắn ở hai đầu các đĩa tạ. Bộ đĩa tạ 
trong phòng tập bao gồm các loại 1kg, 2kg, 5kg, 
10kg, 15kg và 20kg với số lượng mỗi loại là đủ 
Gi¸o viªn: TrÇn L­¬ng V­¬ng Trang 7 Trường THPT Chuyên Võ Nguyên Giáp
 t:= t+j div 5; j := j mod 5;
 t:= t+j div 2; j := j mod 2;
 B[i]:= t+j ;
 Nếu sử dụng mảng hằng C với C i là số lần lắp đĩa tối thiểu để làm tăng trọng 
lượng lên i kg (i = 0 ÷ 19). 
 C :array[0..19] of byte; 
 = (0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 1, 2, 2, 3, 3, 1, 2, 2, 3, 3);
 Việc tính Bi (i:= 0 ÷ 100) lúc này chỉ cần sử dụng vòng lặp:
 For i:=0 to 19 do B[i]:=C[i];
 For i:= 20 to 100 do B[i]:= i div 20 + B[i mod 20];
 Lời giải của bài toán có thể nhận được bằng cách duyệt tất cả các cách tháo 
lần lượt đĩa tạ n, n-1, n-2, . . ., 2, 1.
 Bảng phương án còn là công cụ sắc bén với các loại bài toán liên quan tới 
phát hiện, nhận dạng chu trình. Nó giúp ta đạt được hiệu quả O(n) và trong nhiều 
trường hợp – O(1)!
4.2. Bài toán Thỏ nhặt cà rốt CARROT.???
 Các con thú nuôi trong chuồng ở vườn 
bách thú thường ít có điều kiện vận động. Điều 
này vừa có hại cho sức khỏe của thú nuôi, vừa 
làm làm giảm hứng thú của khách tham quan. 
Để khắc phục điều đó, Ban giám đốc cho đặt 
một cái thang có n bậc trong chuồng thỏ. Đến 
giờ cho ăn người ta đặt cà rốt - thứ khoái khẩu 
nhất của thỏ, lên bậc trên cùng của thang. Thỏ phải nhảy theo các bậc thang để lấy 
cà rốt. Mỗi bước nhảy thỏ có thể vượt được k bậc (1 ≤ k ≤ n ≤ 300). Có thể có 
nhiều cách nhảy để lấy cà rốt. Hai cách nhảy gọi là khác nhau nếu tồn tại một bậc 
thỏ tới được ở một cách nhảy và bị bỏ qua ở cách kia. Ví dụ, với n = 4 và k = 3 có 
tất cả 7 cách lấy cà rốt khác nhau: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1.
Yêu cầu: Cho k và n. Hãy xác định số cách khác nhau thỏ có thể thực hiện để lấy 
cà rốt.
Dữ liệu vào: Ghi trong file văn bản CARROT.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương t là số lượng cặp k và n (1 ≤ t ≤ 50).
Gi¸o viªn: TrÇn L­¬ng V­¬ng Trang 9 Trường THPT Chuyên Võ Nguyên Giáp
 F[0] := 1;
 For i:=1 to k do
 For j:=1 to i-1 do
 F[i] := F[i] + F[j];
 For i:=k+1 to n do
 For j:= i - k to i – 1 do
 F[i] := F[i] + F[j];
 End; 
 2. Cho f0 = 1, fi = 0, i = -k+1 ÷ -1,
 d) Khai báo: Nếu áp dụng cách chuẩn bị giá trị đầu thứ 2 thì cần khai báo:
 Var f:array[-300..300] of int64;
 Procedure Process;
 Var i, j:Longint;
 Begin
 F[0] := 1;
 For i:=-k+1 to -1 do F[i] := 0;
 For i:= 1 to n do
 For j:= i - k to i – 1 do 
 F[i] := F[i] + F[j];
 End; 
 e) Nếu sử dụng cách chuẩn bị giá trị đầu thứ 2 thì phải tính với i = 1 ÷ n,
 f) Kết quả: giá trị fn.
Lưu ý: - Bài toán này có thể áp dụng giải thuật tìm kiếm quay lui (Back Tracking).
 - Kiểu dữ liệu ở đây chưa thật quan trọng, nó sẽ được xác định chính xác 
trong quá trình hiệu chỉnh chương trình, khi thử nghiệm với k = n =300.
 Trần Lương Vương
Gi¸o viªn: TrÇn L­¬ng V­¬ng Trang 11