14/04/2008
1
BÀI TOÁN QUY HOẠCH ĐỘNG
BÀI

TOÁN

QUY

HOẠCH

ĐỘNG
(DYNAMIC PROGRAMMING)
Phạm Thế Bảo
Khoa Toán – Tin học
Trường Đại học Khoa học Tự nhiên Tp.HCM
Nội dung
• Kỹ thuậtchiađể trị thường dẫntớigiảithuật
đệ
quy
Æ
có
giải
thuật
có
thời
gian
mũ
và
giải
đệ

tqu
ả
c
á
c
bài
to
á
ncont
h
eo quy
l
u
ậ
t
nào đó để có kếtquả củabàitoánbanđầu Æ
quy hoạch động
Phạm Thế Bảo
14/04/2008
2
Thuật giải
1. Tạobảng bằng cách:
ố
a. Gán giá trị mộ
t
s
ố
ô nào đó.
b. Gán giá trị cho các ô khác nhờ vào giá trị của các
ôtrước.

– Không tìm được công thứctruyhồi.
–
Số
lượng
bài
toán
con
cần
giải
và
lưu
trữ
kết
quả
rất
Số
lượng
bài
toán
con
cần
giải
và
lưu
trữ
kết
quả
rất
lớn.
– Việckếthợplờigiảicủa các bài toán con chưachắc

k
n
k
n
C
C
−
⎧
=
⎨
+
⎩
}
Phạm Thế Bảo
Đánh giá
• Gọi T(n) là thời gian tính C
n
k
,
ta có T
(
1
)
=C
1
và T
(
n
)
=

Phạm Thế Bảo
0
1
1 11
2 11
3 11
4 11
Tamgiác Pascal
• Thuậtgiảimới:
int ** Comb(int n, int k){
C[0,0]=1;
for i=1 to n do
C[i,0]=1;
C[i,i]=1;
for j=1 to i-1 do
C[i,j]=C[i-1,j-1]+C[i-1,j];
endfor
return C;
}
}
• Vòng lặp for j thựchiệni-1 lần. Vòng lặpilặp
n lần Æ
Phạm Thế Bảo
14/04/2008
5
Bài toán cái ba lô
• Giả sử X[k,V] là số lượng đồ vậtkđượcchọn,
F[
kV
]

ta tính X[1,V] và F[1,V] với V=1 W như sau:
X[
1
V] V
di
à
F[
1
V] X[
1
V]*
–
X[
1
,
V]
=
V
di
vg
1
v
à
F[
1
,
V]
=
X[
1

là
F[
kV
]
=
F[k
-
giá
trị
k
loại
đồ
vật
đã
được
chọn
là
F[
k
,
V
]F[k
1,U]+x
k
*v
kvới
x
k
từ 0 đếny
k

F[
k
,
V
]=max{F[k
-
1
,
V
-
x
k
*
g
k
]+
x
k
*
v
k
}
với
x
k
chạy
từ
0
đến(Vdivg
k

0123456 7 8 9
1 000000 1414182 2 8 2 123
2 00000040515180 9 1 10212 0
3 00000040506180 9 0 10 0 120
4 0000314062719310 2 12 413 3
v
k
5 0011304060709010 0 12 013 0
Đồ vậtg
i
v
i
133
245
356
4
2
3
• Cách tính:
– Dòng thứ nhất, dùng công thức X[1,V]=V div g
1
và F[1,V]=X[1,V]*v
1
– Từ dòng 2 đến dòng 5 dùng công thứctruyhồi F[k,V]=max{F[k-1, V-
x
k
*g
k
]+x
k

• Ví dụ: V=W=9
– Xét k=5, có X[5,9]=0 Æ không chọn
– Xét k=4, có X[4,9]=3 Æ chọn3đồ vậtloại 4, tính lại
V=9-3*2=3.
– Xét k=3, có X[3,3]=0 Æ không chọn
– Xét k=2, có X[2,3]=0 Æ không chọn
– Xét k=1, có X[1,3]=1 Æ chọn1đồ vậtloại 1, tính lại
V=3-1*3=0
– Tổng trọng lượng các vật trong ba lô=
– Tổng giá trị các vật trong ba lô =
Phạm Thế Bảo
Bài tập: cài đặtchương trình
Bài toán ngườigiaohàng
• Chúng ta cũng có thể dùng quy hoạch động để
iải
ết
g
iải
quy
ết
:
– ĐặtS={x
1
,x
2
,…,x
k
}làtập con các cạnh của đồ thị
G=(V,E). Ta nói một đường đitừ v đếnwphủ lên S
nếuP={v,x

g
đ
ộ
dài là d
(
H
min
)
=d
(
o
,
o
,
V-
{
o
}),
vớiolàm
ột
đỉnh
g
ộ
(
min
)(
,,
{}),
ộ
nào đó trong V.