Một số bài toán quy hoạch động điển hình

à số đồng xu ít nhất nếu đổi 
t đồng ra i loại tiền xu (từ 1 đến i). Công thức tính L(i,t) như sau: 
• L(i,0)=0; 
• L(0,t)= ∞ với t>0. 
• L(i,t)=L(i–1,t) nếu t<ai. 
• L(i,t)=min(L(i–1,t), L(i,t–ai)+1) nếu t ≥ai. 
Công thức này khác công thức của bài xếp balô ở chỗ: dùng hàm min chứ không phải hàm 
max (vì cần tìm cách chọn ít hơn) và nếu chọn đồng xu thứ i thì L(i,t)=L(i,t–ai)+1 (vì ta vẫn 
còn được chọn đồng xu thứ i đó nữa), khác với khi xếp balô là: nếu chọn đồ vật thứ i thì 
L(i,t)=L(i–1,t–ai)+bi vì đồ vật i chỉ được chọn một lần. 
V. Nhân ma trận 
1. Mô hình 
Nhân một ma trận kích thước m×n với một ma trận n×p, số phép nhân phải thực hiện là 
m.n.p. Mặt khác phép nhân các ma trận có tính kết hợp, tức là: 
(A.B).C = A.(B.C) 
Do đó khi tính tích nhiều ma trận, ta có thể thực hiện theo các trình tự khác nhau, mỗi trình tự 
tính sẽ quyết định số phép nhân cần thực hiện. 
Cho N ma trận A1,A2An, ma trận Ai có kích thước là di–1
×
di. Hãy xác định trình tự nhân ma 
trận A1.A2An sao cho số phép nhân cần thực hiện là ít nhất. 
2. Công thức 
Gọi F(i,j) là số phép nhân để tính tích các ma trận từ Aiđến Aj (Ai.Ai+1....Aj). 
• F(i,i)=0. 
• F(i,i+1)=di–1.di.di+1 
• F(i,j) = min(F(i,k)+F(k+1,j)+di–1.dk.dj với k=i+1,i+2,...j–1) 
Công thức hơi phức tạp nên tôi xin giải thích như sau: 
• F(i,i)=0 là hiển nhiên. 
• F(i,i+1) là số phép nhân khi nhân Ai và Ai+1. Ai có kích thước di–1
×
di, Ai+1 có kích thước 
di×di+1, do đó F(i,i+1)=di–1
.d
i
.d
i+1
.
• Với j>i+1 thì ta thấy có thể tính Ai.Ai+1....Aj bằng cách chọn một vị trí k nào đó để đặt 
ngoặc theo trình tự: 
Ai.Ai+1....Aj = (Ai..Ak).(Ak+1..Aj) 
Ma trận kết quả của phép nhân (Ai..Ak) có kích thước di–1
×
dk, ma trận kết quả của phép nhân 
(Ak+1..Aj) có kích thước dk×dj. Với cách đặt đó ta sẽ mất F(i,k) phép nhân để có kết quả trong 
dấu ngoặc thứ nhất, mất thêm F(k+1,j) phép nhân để có kết quả trong dấu ngoặc thứ hai, và 
cuối cùng mất di–1.dk.dj để nhân 2 ma trận kết quả đó. Từ đó tổng số phép nhân của cách đặt 
đó là: F(i,k)+F(k+1,j)+di–1.dk.dj. 
Ta chọn vị trí k cho số phép nhân ít nhất. 
 Trang10 
 3. Cài đặt 
Bảng phương án là một mảng 2 chiều F để lưu F(i,j). Chú ý khi cài đặt là để tính được F(i,j), 
ta phải tính F(i,k) và F(k+1,j) trước. Phương pháp đơn giản để làm điều đó là phương pháp đệ 
quy có nhớ. 
Tuy nhiên dựa vào nhận xét là trong công thức QHĐ: j–i lớn hơn k–i và j–k, ta có thể tính 
theo trình tự khác: tính các phần tử F(i,j) với j–i từ nhỏ đến lớn (không phải là tính các giá 
trị F(i,j) với i,j từ nhỏ đến lớn như vẫn làm). Với cách đó, khi tính đến F(i,j) thì ta đã có F(i,k) 
và F(k+1,j). 
Đoạn chương trình tính bảng phương án như sau: 
for i:=1 to n do F[i,i]:=0; 
for i:=1 to n–1 do 
 F[i,i+1] := d[i–1]*d[i]*d[i+1]; 
for m:=2 to n–1 do begin 
 for i:=1 to n–m do begin 
 j:=i+m; F[i,j]:=oo; 
 for k:=i+1 to j–1 do 
 F[i,j]:=min(F[i,j], 
 F[i,k]+F[k+1,j]+d[i–1]*d[k]*d[j]); 
 end; 
end; 
Với cách cài đặt trên,chi phí không gian là O(n2), chi phí thời gian là O(n3) (đây là bài toán có 
chi phí lớn nhất trong tất cả các bài toán QHĐ thường gặp). 
4. Một số bài toán khác 
a) Chia đa giác 
Cho một đa giác lồi N đỉnh. Bằng các đường chéo không cắt nhau, ta có thể chia đa giác thành 
N–2 tam giác. Hãy xác định cách chia có tổng các đường chéo ngắn nhất. 
Hướng dẫn: Để đơn giản ta coi mọi đoạn thẳng nối 2 đỉnh đều là “đường chéo” (nếu nối 2 
đỉnh trùng nhau hoặc 2 đỉnh liên tiếp thì có độ dài bằng 0). 
Gọi F(i,j) là tổng độ dài các đường chéo khi chia đa giác gồm các đỉnh từ i đến j thành các 
tam giác. Nếu j<i+3 thì đa giác đó có ít hơn 4 đỉnh, không cần phải chia nên F(i,j)=0. Ngược 
lại ta xét cách chia đa giác đó bằng cách chọn một đỉnh k nằm giữa i,j và nối i,j với k. Khi đó 
F(i,j)=F(i,k)+F(k,j)+d(i,k)+d(k,j); d(i,k) là độ dài đường chéo (i,k). 
Tóm lại công thức QHĐ như sau: 
• F(i,j)=0 với j<i+3. 
• F(i,j)=min(F(i,k)+F(k,j)+d(i,k)+d(k,j) với k=i+1,...j–1). 
F(1,n) là tổng đường chéo của cách chia tối ưu. 
b) Biểu thức số học (IOI 1999) 
Cho biểu thức a1•a2••an, trong đó ai là các số thực không âm và • là một phép toán + hoặc 
× cho trước. Hãy đặt các dấu ngoặc để biểu thức thu được có kết quả lớn nhất. 
Hướng dẫn: Gọi F(i,j) là giá trị lớn nhất có thể có của biểu thức ai•ai+1••aj. Dễ thấy nếu i=j 
thì F(i,j)=ai, nếu j=i+1 thì F(i,j)=ai•aj. Nếu j>i+1 thì có thể tính biểu thức ai•ai+1••aj bằng 
cách chia thành 2 nhóm: (ai•ai+1••ak)•(ak+1••aj), Khi đó F(i,j)=F(i,k)•F(k+1,j). 
Tóm lại, công thức QHĐ là: 
 Trang11 
 • F(i,i)=ai 
• F(i,i+1)=ai•ai+1 
• F(i,j)=max(F(i,k)•F(k+1,j) với k=i+1,i+2,..j–1). 
(Chú là là các hạng tử của dãy đều không âm và các phép toán là + hoặc × nên F(i,k) và 
F(k+1,j) đạt max thì F(i,k)•F(k+1,j) cũng đạt max). 
VI. Ghép cặp 
1.Mô hình 
Có n lọ hoa sắp thẳng hàng và k bó hoa được đánh số thứ tự từ nhỏ đến lớn. Cần cằm k bó hoa trên 
vào n lọ sao cho hoa có số thứ tự nhỏ phải đứng trước hoa có số thứ tự lớn. Giá trị thẩm mỹ tương ứng 
khi cắm hoa i vào lọ thứ j là v(i,j) Hãy tìm 1 cách cắm sao cho tổng giá trị thẫm mỹ là lớn nhất. Chú ý 
rằng mỗi bó hoa chỉ được cắm vào 1 lọ và mỗi lọ cũng chỉ cắm được 1 bó hoa. (IOI –1999) 
2. Công thức : 
Nhận xét rằng bài toán nêu trên là một bài toán ghép cặp có yêu cầu về thứ tự nên ta có thể 
giải quyết bằng phương pháp QHĐ. 
Hàm mục tiêu : f: tổng giá trị thẩm mỹ của cách cắm. 
Giá trị thẩm mỹ phụ thuộc vào các hoa và các lọ đang được xét nên ta sẽ dùng mảng 2 chiều 
để lưu bảng phương án. 
L(i,j): tổng giá trị thẩm mỹ lớn nhất khi xét đến hoa i và lọ j. Khi tính L(i,j) hoa đang xét sẽ là 
hoa i và lọ j. 
• Nếu i = j. Chỉ có một cách cắm L(i,i):= v[1,1]+v[2,2]+...v[i,i] 
• Nếu i>j . Không có cách cắm hợp lý 
• Nếu i<j : Có 2 trường hợp xảy ra: 
Cắm hoa i vào lọ j. Tổng giá trị thẩm mỹ là L(i-1,j-1)+v(i,j). (Bằng tổng giá trị trước khi 
cắm cộng với giá trị thẩm mỹ khi cắm hoa i vào lọ j) 
Không cắm hoa i vào lọ j (có thể cắm vào lọ trước j), giá trị thẫm mỹ của cách cắm là như 
cũ : L(i,j-1) 
3. Cài đặt : 
L[i,j]:= -maxint; 
For i:=1 to k do 
 For j:=i to n do 
 If i = j then L[i,j]:=sum(i) 
 else 
 if i<j then L[i,j]:=max(L[i-1,j-1]+v[i,j],L[i,j-1]); 
4. Một số bài toán khác 
a) Câu lạc bộ:( Đề thi chọn HSG Tin Hà Nội năm 2000) 
Có n phòng học chuyên đề và k nhóm học được đánh số thứ tự từ nhỏ đến lớn. Cần xếp k 
nhóm trên vào n phòng học sao cho nhóm có số hiệu nhỏ được xếp vào phòng có số hiệu nhỏ, 
nhóm có số hiệu lớn phải được xếp vào phòng có số hiệu lớn.Với mỗi phòng có chứ học sinh, 
các ghế thừa phải được chuyển ra hết, nếu thiếu ghế thì lấy vào cho đủ ghế .Biết phòng i có 
 Trang12 
 a(i) ghế ,nhóm j có b(j) học sinh. Hãy chọn 1 phương án bố trí sao cho tổng số lần chuyển ghế 
ra và vào là ít nhất. 
Hướng dẫn : Khi xếp nhóm i vào phòng j thì số lần chuyển ghế chính là độ chênh lệch giữa 
số ghế trong phòng i và số học sinh trong nhóm. Đặt v[i,j]:=|a(i)-b(j)| 
b) Mua giày (Đề QG bảng B năm 2003) 
Trong hiệu có n đôi giày, đôi giày i có kích thước hi. Có k người cần mua giày, người i cần 
mua đôi giày kích thước si . Khi người i chọn mua đôi giày j thì độ lệch sẽ là |h(i)-s(j)|. Hãy 
tìm cách chọn mua giày cho k người trên sao cho tổng độ lệch là ít nhất. Biết rằng mỗi người 
chỉ mua 1 đôi giày và 1 đôi giày cũng chỉ có một người mua. 
Hướng dẫn : Lập công thức giải như bài Câu lạc bộ. Chú ý chứng minh tính đúng đắn của bổ 
đề heuristic sau :Cho 2 dãy tăng dần các số dương a1a2...an , b1b2...bn. Gọi c1c2...cn là một 
hoán vị của dãy {bn}. Khi đó : |a(1)-b(1)|+ |a(2)-b(2)|+...+ |a(n)-b(n)|< |a(1)-c(1)|+ |a(2)- 
c(2)|+...+ |a(n)-c(n)| 
VII. Di chuyển 
1. Mô hình 
Cho bảng A gồm MxN ô. Từ ô (i,j) có thể di chuyển sang 3 ô (i+1,j), (i+1,j–1) và (i+1,j+1). 
Hãy xác định một lộ trình đi từ hàng 1 đến hàng M sao cho tổng các ô đi qua là lớn nhất. 
2. Công thức 
Gọi F(i,j) là giá trị lớn nhất có được khi di chuyển đến ô (i,j). Có 3 ô có thể đi đến ô (i,j) là (i– 
1,j), (i–1,j–1) và (i–1,j+1). Do đó ta có công thức QHĐ như sau: 
• F(1,j)=A[1,j] 
• F(i,j)=max(F(i–1,j),F(i–1,j–1),F(i–1,j+1))+A[i,j] với i>1 
3. Cài đặt 
Bảng phương án là bảng 2 chiều F[0..m,0..n]. (Tất cả các ô trên biên đều cho giá trị bằng 0). 
Quá trình tính như sau: 
for i:=1 to m do 
 for j := 1 to n do 
 F[i,j]=max[F[i–1,j],F[i–1,j–1],F[i–1,j+1]]+A[i,j]; 
Cách cài đặt này cho chi phí không gian và thời gian đều là O(n2). Ta có thể tiết kiệm không 
gian nhớ bằng cách tính trực tiếp trên mảng A. 
4. Một số bài toán khác 
a) Tam giác (IOI 1994) 
Cho một tam giác gồm các số nguyên không âm. Hãy tính tổng lớn nhất các số trên đường đi 
từ đỉnh tam giác xuống một điểm nào đó ở đáy tam giác nào đó. Tại mỗi ô ta chỉ có đi thẳng 
xuống, sang ô bên trái hoặc bên phải. 
Hướng dẫn: Mô tả các phần tử của tam giác số như một ma trận, A[i,j] là phần tử thứ j trên 
dòng i (với 1≤i≤N và 1≤j≤i). Có 2 ô có thể di chưyển đến ô (i,j) là ô (i–1,j–1) và ô (i–1,j). Gọi 
F(i,j) là tổng lớn nhất có thể có khi đi đến ô (i,j) ta có: 
 Trang13 
 • F(1,1)=A[1,1] 
• F(i,1)=F(i–1,1)+A[i,1] 
• F(i,j)=max(F(i–1,j–1),F(i–1,j))+A[i,j] 
b) Con kiến 
Có một ống hình trụ, khi trải phẳng ra có thể là một bảng MxN ô. Giá trị A[i,j] là lượng thức 
ăn có ở ô ở dòng i cột j. Một con kiến xuất phát từ một ô ở mép bên trái của hình trụ và bò 
sang mép bên phải. Từ ô (i,j) kiến có thể bò sang 1 trong 3 ô (i–1,j+1), (i,j+1) hoặc (i+1,j+1). 
(Chú ý: vì ống hình trụ nên kiến đang ở dòng 1 có thể bò xuống dòng M và ngược lại). Bò qua 
ô nào thì kiến mang theo toàn bộ lượng thức ăn ở ô đó. Hãy tìm đường đi mà kiến kiếm được 
nhiều thức ăn nhất. 
Hướng dẫn: Để xử lí tình huống hình trụ, ta lưu dòng 0 là dòng M và dòng M+1 là dòng 1. 
Khi đó tương tự như bài toán ban đầu, gọi F(i,j) là lượng thức ăn kiến có được khi bò đến ô 
(i,j), ta thiết lập được công thức QHĐ sau: 
• F(i,1)=A[i,1] 
• F(i,j)=max(F(i–1,j–1),F(i,j–1),F(i+1,j+1))+A[i,j] với j>1 
 Trang14