Chuyên đề tin học - Lý thuyết quy hoạch động
Khi giải một bài toán con, cần đến nghiệm của bài toán con nhỏ hơn, ta chỉ cần tìm kiếm trong bảng, không cần phải giải lại. Chính vì thế mà giải thuật nhận được bằng phương pháp này rất có hiệu quả.
Chuyeân ñeà Tin hoïc
PHÖÔNG PHAÙP
QUY HOAÏCH ÑOÄNG
Bieân soaïn: Traàn Quang Quaù
Giaùo vieân tröôøng PTTH chuyeân Löông Theá Vinh, Bieân Hoaø
Thaùng 4 naêm 2002
1. GIÔÙI THIEÄU:
Phöông phaùp quy hoaïch ñoäng (dynamic programming) laø moät kó thuaät ñöôïc
aùp duïng ñeå giaûi nhieàu lôùp baøi toaùn, ñaëc bieät laø caùc baøi toaùn toái öu.
Phöông phaùp quy hoaïch ñoäng duøng kó thuaät bottom up (ñi töø döôùi leân):
Xuaát phaùt töø caùc tröôøng hôïp rieâng ñôn giaûn nhaát, coù theå tìm ngay ra nghieäm.
Baèng caùch keát hôïp nghieäm cuûa chuùng, ta nhaän ñöôïc nghieäm cuûa baøi toaùn côõ lôùn
hôn. Cöù theá tieáp tuïc, chuùng ta seõ nhaän ñöôïc nghieäm cuûa baøi toaùn. Trong quaù trình
“ñi töø döôùi leân” chuùng ta seõ söû duïng moät baûng ñeå löu giöõ lôøi giaûi cuûa caùc baøi toaùn
con ñaõ giaûi, khoâng caàn quan taâm ñeáùn noù ñöôïc söû duïng ôû ñaâu sau naøy.
Khi giaûi moät baøi toaùn con, caàn ñeán nghieäm cuûa baøi toaùn con nhoû hôn, ta chæ
caàn tìm kieám trong baûng, khoâng caàn phaûi giaûi laïi. Chính vì theá maø giaûi thuaät nhaän
ñöôïc baèng phöông phaùp naøy raát coù hieäu quaû.
1.1. Öu ñieåm cuûa phöông phaùp quy hoaïch ñoäng:
Chöông trình chaïy nhanh.
•
1.2. Phaïm vi aùp duïng cuûa phöông phaùp quy hoaïch ñoäng:
Caùc baøi toaùn toái öu: nhö tìm xaâu con chung daøi nhaát, baøi toaùn baloâ, tìm
•
ñöôøng ñi ngaén nhaát, baøi toaùn OÂtoâmat vôùi soá pheùp bieán ñoåi ít nhaát, …
Caùc baøi toaùn coù coâng thöùc truy hoài.
•
1.3. Haïn cheá cuûa phöông phaùp quy hoaïch ñoäng:
Phöông phaùp quy hoaïch ñoäng khoâng ñem laïi hieäu quaû trong caùc tröôøng hôïp sau:
Söï keát hôïp lôøi giaûi cuûa caùc baøi toaùn con chöa chaéc cho ta lôøi giaûi cuûa baøi
•
toaùn lôùn.
Soá löôïng caùc baøi toaùn con caàn giaûi quyeát vaø löu tröõ keát quaû coù theå raát
•
lôùn, khoâng theå chaáp nhaän ñöôïc.
Khoâng tìm ñöôïc coâng thöùc truy hoài.
•
Quy hoaïch ñoäng 2 Traàn Quang Quaù
2. CAÁU TRUÙC CHUNG CUÛA CHÖÔNG TRÌNH CHÍNH:
BEGIN {Chöông trình chính}
Chuaån bò: ñoïc döõ lieäu vaø khôûi gaùn moät soá giaù trò;
Taïo baûng;
Tra baûng vaø in keát quaû;
END.
3. PHÖÔNG PHAÙP QUY HOAÏCH ÑOÄNG:
1) Tính nghieäm toái öu cuûa baøi toaùn trong tröôøng hôïp rieâng ñôn giaûn nhaát.
2) Tìm caùc coâng thöùc ñeä quy bieåu dieãn nghieäm toái öu cuûa baøi toaùn lôùn thoâng
qua nghieäm toái öu cuûa caùc baøi toaùn con.
3) Tính nghieäm toái öu töø döôùi leân (bottom up) vaø ghi laïi caùc nghieäm toái öu cuûa
caùc baøi toaùn con ñaõ tính ñeå söû duïng sau naøy.
4. VÍ DUÏ:
4.1. Daõy Fibonaci:
Ñeà baøi: In ra maøn hình 20 soá haïng ñaàu cuûa daõy Fibonaci.
Bieát: F1 = 1
F2 = 1
F3 = 2 Fi = Fi-1 + Fi-2 vôùi i > 2
F4 = 3
Giaûi thuaät:
1) Tính nghieäm cuûa baøi toaùn trong tröôøng hôïp rieâng ñôn giaûn nhaát.
F1 = F2 = 1
2) Tìm caùc coâng thöùc ñeä quy bieåu dieãn nghieäm toái öu cuûa baøi toaùn lôùn thoâng
qua nghieäm toái öu cuûa caùc baøi toaùn con.
Fi = Fi-1 + Fi-2 vôùi i > 2
Möôøi soá haïng ñaàu cuûa daõy Fibonaci:
i 1 2 3 4 5 6 7 8 9 10
F[i] 1 1 2 3 5 8 13 21 34 55
4.2. Toå hôïp chaäp k cuûa n phaàn töû:
k
Ñeà baøi: Tính caùc phaàn töû cuûa maûng C[n, k] = Cn = soá toå hôïp chaäp k
cuûa n phaàn töû, vôùi 0 ≤ k ≤ n ≤ 20.
o n
Bieát Cn = Cn = 1
k k-1 k
Cn = Cn-1 + Cn-1
Quy hoaïch ñoäng 3 Traàn Quang Quaù
Giaûi thuaät:
1) Tính nghieäm cuûa baøi toaùn trong tröôøng hôïp rieâng ñôn giaûn nhaát.
For i := 1 To n Do
Begin
C[0, i] := 1;
C[i, i] := 1;
End;
2) Tìm caùc coâng thöùc ñeä quy bieåu dieãn nghieäm toái öu cuûa baøi toaùn lôùn thoâng
qua nghieäm toái öu cuûa caùc baøi toaùn con.
For i := 2 To n Do
For j := 1 To i-1 Do
C[i, j] := C[i-1,j-1] + C[i-1,j];
n k 0 1 2 3 4 5
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
3) Coù theå caûi tieán: duøng 2 maûng moät chieàu thay cho 1 maûng hai chieàu.
4.3. Tìm daõy con khoâng giaûm daøi nhaát:
Ñeà baøi: Cho moät daõy n soá nguyeân. Haõy loaïi boû khoûi daõy moät soá phaàn töû ñeå
ñöôïc moät daõy con khoâng giaûm daøi nhaát. In ra daõy con ñoù.
Ví duï: Input:
10
2 6 -7 5 8 1 -3 5 15 9
Keát quaû tìm ñöôïc daõy con khoâng giaûm daøi nhaát coù 4 phaàn töû:
-7 -3 5 9
Giaûi thuaät:
1) Toå chöùc döõ lieäu:
Goïi A laø daõy ban ñaàu.
Goïi B[i] laø soá phaàn töû cuûa daõy con daøi nhaát trong daõy coù i phaàn töû ñaàu tieân
A[1] .. A[i] vaø A[i] ñöôïc choïn laøm phaàn töû cuoái. (i ∈ [1, n])
C laø daõy con khoâng giaûm daøi nhaát tìm ñöôïc.
Truoc[i] laø chæ soá cuûa phaàn töû tröôùc phaàn töû i (caùc phaàn töû giöõ laïi C).
2) Giaûi thuaät taïo baûng: (Tính maûng B vaø maûng Tröôùc)
Tröôøng hôïp ñôn giaûn nhaát: daõy chæ coù 1 phaàn töû, thì B[1] := 1;
For i töø 2 ñeán n Do
• Xeùt vôùi moïi j < i vaø A[j] Quy hoaïch ñoäng 4 Traàn Quang Quaù
Trong ví duï treân:
i 1 2 3 4 5 6 7 8 9 10
Daõy A[i] 2 6 -7 5 8 1 -3 5 15 9
B[i] 1 2 1 2 3 2 2 3 4 4
Truoc[i] 0 1 1 3 4 3 3 7 8 8
Daõy con khoâng giaûm daøi nhaát coù 4 phaàn töû: -7 -3 5 9
Procedure TaoBang;
Var i, j, BMax, chiSo :byte;
Begin
B[1] := 1;
For i := 2 to n do
begin
BMax := 0;
For j := i-1 DownTo 1 Do
If (A[j] BMax)then
begin
BMax := B[j];
chiSo := j;
end;
B[i] := BMax + 1;
Truoc[i] := chiSo;
end;
End;
Coù theå caûi tieán khoâng caàn duøng bieán BMax vaø chiSo
3) Tra baûng: ñeå tìm caùc phaàn töû cuûa daõy C:
a) Tìm phaàn töû lôùn nhaát cuûa maûng B. (öùng vôùi chæ soá ChiSoMax).
Phaàn töû lôùn nhaát cuûa maûng B chính laø soá phaàn töû cuûa daõy C.
b) A[ChiSoMax] laø phaàn töû cuoái cuûa daõy C. Nhôø vaøo maûng Tröôùc, ta tìm caùc
phaàn töû coøn laïi trong daõy C: tìm ngöôïc töø cuoái daõy leân ñaàu daõy.
Procedure TraBang;
Var chiSo, ChiSoMax, i : byte;
Begin
ChiSoMax := n;
for i:= n-1 downto 1 do
if B[i] > B[ChiSoMax] then
ChiSoMax := i;
chiSo := ChiSoMax;
for i := B[ChiSoMax] downto 1 do
begin
C[i]:= A[chiSo];
chiSo := Truoc[chiSo];
end;
End;
Quy hoaïch ñoäng 5 Traàn Quang Quaù
4.4. Baøi toaùn baloâ 1:
Ñeà baøi: Cho n moùn haøng (n ≤ 50). Moùn thöù i coù khoái löôïng laø A[i] (soá
nguyeân). Caàn choïn nhöõng moùn haøng naøo ñeå boû vaøo moät ba loâ sao toång khoái löôïng
cuûa caùc moùn haøng ñaõ choïn laø lôùn nhaát nhöng khoâng vöôït quaù khoái löôïng W cho
tröôùc. (W ≤ 100). Moãi moùn chæ choïn 1 hoaëc khoâng choïn.
Input:
nW
A[1] A[2] … A[n]
Ví duï:
4 10
5 2 4 3
OutPut:
Toång khoái löôïng cuûa caùc moùn haøng boû vaøo ba loâ.
Khoái löôïng cuûa caùc moùn haøng ñaõ choïn.
Trong ví duï treân:
Toång khoái löôïng cuûa caùc moùn haøng boû vaøo ba loâ laø 10
Khoái löôïng caùc moùn haøng ñöôïc choïn: 5 2 3
Höôùng giaûi:
1) Toå chöùc döõ lieäu:
Fx[k, v] laø toång khoái löôïng cuûa caùc moùn haøng boû vaøo ba loâ khi coù k moùn
haøng ñaàu tieân ñeå choïn vaø khoái löôïng toái ña cuûa ba loâ laø v.
Vôùi k ∈ [1, n], v ∈ [1, W].
Noùi caùch khaùc: Khi coù k moùn ñeå choïn, Fx[k, v] laø khoái löôïng toái öu khi khoái
löôïng toái ña cuûa ba loâ laø v.
Khoái löôïng toái öu luoân nhoû hôn hoaëc baèng khoái löôïng toái ña: Fx[k, v] ≤ v
Ví duï: Fx[4, 10] = 8 Nghóa laø trong tröôøng hôïp toái öu, toång khoái löôïng cuûa
caùc moùn haøng ñöôïc choïn laø 8, khi coù 4 moùn ñaàu tieân ñeå choïn (töø moùn thöù 1 ñeán
moùn thöù 4) vaø khoái löôïng toái ña cuûa ba loâ laø 10. Khoâng nhaát thieát caû 4 moùn ñeàu
ñöôïc choïn.
2) Giaûi thuaät taïo baûng:
* Tröôøng hôïp ñôn giaûn chæ coù 1 moùn ñeå choïn: Ta tính Fx[1, v] vôùi moïi v:
Neáu coù theå choïn (nghóa laøkhoái löôïng toái ña cuûa ba loâ >= khoái löôïng cuûa
caùc moùn haøng thöù 1), thì choïn: Fx[1, v] := A[1];
Ngöôïc laïi ( v < A[1] ), khoâng theå choïn, nghóa laø Fx[1, v] := 0;
Quy hoaïch ñoäng 6 Traàn Quang Quaù
* Giaû söû ta ñaõ tính ñöôïc Fx[k–1 , v ] ñeán doøng k–1, vôùi moïi v ∈ [1, W].
Khi coù theâm moùn thöù k ñeå choïn, ta caàn tính Fx[k , v] ôû doøng k, vôùi moïi v∈[1,W]
Neáu coù theå choïn moùn haøng thöù k (v >= A[k]), thì coù 2 tröôøng hôïp:
– Tröôøng hôïp 1: Neáu choïn theâm moùn thöù k boû vaøo ba loâ, thì
Fx[k, v] := Fx[k–1, u ] + A[k];
Vôùi u laø khoái löôïng coøn laïi sau khi choïn moùn thöù k. u = v – A[k]
– Tröôøng hôïp 2: Ngöôïc laïi, khoâng choïn moùn thöù k, thì
Fx[k, v] := Fx[k–1, v ];
Trong 2 tröôøng hôïp treân ta choïn tröôøng hôïp naøo coù Fx[k, v] lôùn hôn.
Ngöôïc laïi (v < A[k]), thì khoâng theå choïn, nghóa laø Fx[k, v] := Fx[k–1, v];
Toùm laïi: coâng thöùc ñeä quy laø:
If v >= A[k] Then
Fx[k,v] := Max(Fx[k-1, v - A[k]] + A[k] , Fx[k-1,v])
Else
Fx[k,v] := Fx[k-1, v];
Döôùi ñaây laø baûng Fx[k,v] tính ñöôïc trong ví duï treân:
k v 1 2 3 4 5 6 7 8 9 10
1 0 0 0 0 5 5 5 5 5 5
2 0 2 2 2 5 5 7 7 7 7
3 0 2 2 4 5 6 7 7 9 9
4 0 2 3 4 5 6 7 8 9 10
Procedure TaoBang;
Var k ,v : integer;
Begin
For v:=1 to W do
If v >= A[1] then Fx[1, v] := A[1]
Else Fx[1, v] := 0;
For k:= 2 to n do
for v:=1 to W do
If v >= A[k] then
Fx[k,v]:= Max(Fx[k-1,v-A[k]]+ A[k], Fx[k-1,v])
Else
Fx[k,v]:=Fx[k-1,v];
End;
3) Giaûi thuaät tra baûng ñeå tìm caùc moùn haøng ñöôïc choïn:
Chuù yù: Neáu Fx[k, v] = Fx[k–1, v] thì moùn thöù k khoâng ñöôïc choïn.
Fx[n, W] laø toång khoái löôïng toái öu cuûa caùc moùn haøng boû vaøo ba loâ.
Böôùc 1: Baét ñaàu töø k = n, v = W.
Böôùc 2: Tìm trong coät v, ngöôïc töø döôùi leân, ta tìm doøng k sao cho
Fx[k,v] > Fx[k–1, v].
Ñaùnh daáu moùn thöù k ñöôïc choïn: Choïn[k] := true;
Böôùc 3: v := Fx[k, v] – A[k].
Neáu v > 0 thì thöïc hieän böôùc 2, ngöôïc laïi thöïc hieän böôùc 4
Böôùc 4: Döïa vaøo maûng Choïn ñeå in ra caùc moùn haøng ñöôïc choïn.
Quy hoaïch ñoäng 7 Traàn Quang Quaù
Procedure TraBang;
var k, v: Integer;
Begin
k := n;
v := w;
FillChar(chon,SizeOf(chon),false);
Repeat
While Fx[k,v] = Fx[k-1,v] do Dec(k);
chon[k]:= True;
v := Fx[k,v] - A[k];
Until v = 0;
For k := 1 to n do
If chon[k] then Write(A[k]:5);
Writeln;
End;
4.5. Baøi toaùn chia keïo:
Ñeà baøi: Cho n goùi keïo (n ≤ 50). Goùi thöù i coù A[i] vieân keïo. Caàn chia caùc
goùi keïo naøy cho 2 em beù sao cho toång soá vieân keïo moãi em nhaän ñöôïc cheânh
leäch ít nhaát. Moãi em nhaän nguyeân goùi. Khoâng môû goùi keïo ra ñeå chia laïi.
Haõy lieät keâ soá keïo trong caùc goùi keïo moãi em nhaän ñöôïc.
Input:
n
A[1] A[2] … A[n]
Output: Soá keïo trong caùc goùi keïo moãi em nhaän ñöôïc, vaø toång soá keïo moãi
em nhaän ñöôïc.
Höôùng giaûi:
Goïi S laø toång soá vieän keïo S := A[1] + A[2] + … + A[n];
S2 laø nöûa toång soá keïo: S2 := S div 2;
Cho em beù thöù nhaát choïn tröôùc nhöõng goùi keïo sao cho toång soá vieân keïo
maø em nhaän ñöôïc laø lôùn nhaát nhöng khoâng vöôït quaù soá keïo S2.
Goùi keïo naøo em beù thöù nhaát khoâng choïn thì em beù thöù hai choïn.
Baøi toaùn ñöôïc ñöa veà baøi ba loâ 1.
4.6. Baøi toaùn baloâ 2:
Ñeà baøi: Cho n moùn haøng (n ≤ 50). Moùn thöù i coù khoái löôïng laø A[i] vaø giaù
trò C[i] (soá nguyeân). Caàn choïn nhöõng moùn haøng naøo ñeå boû vaøo moät ba loâ sao
toång giaù trò cuûa caùc moùn haøng ñaõ choïn laø lôùn nhaát nhöng toång khoái löôïng cuûa
chuùng khoâng vöôït quaù khoái löôïng W cho tröôùc (W ≤ 100).
Moãi moùn chæ choïn 1 hoaëc khoâng choïn.
Input:
nW
A[1] C[1]
A[2] C[2]
…
A[n] C[n]
Quy hoaïch ñoäng 8 Traàn Quang Quaù
Ví duï:
5 13
3 4
4 5
5 6
2 3
1 1
OutPut:
Toång giaù trò cuûa caùc moùn haøng boû vaøo ba loâ.
Khoái löôïng vaø giaù trò cuûa caùc moùn haøng ñaõ choïn.
Trong ví duï treân:
Toång giaù trò cuûa caùc moùn haøng boû vaøo ba : 16
Caùc moùn ñöôïc choïn:
1(3, 4) 2(4, 5) 3(5, 6) 5(1, 1)
Höôùng giaûi:
Töông töï baøi ba loâ 1, nhöng Fx[k, v] laø giaù trò lôùn nhaát cuûa ba loâ khi coù k
moùn haøng ñaàu tieân ñeå choïn vaø khoái löôïng toái ña cuûa ba loâ laø v.
Coâng thöùc ñeä quy laø:
If v >= A[k] Then
Fx[k,v]:= Max(Fx[k-1, v-A[k]] + C[k], Fx[k-1,v])
Else
Fx[k,v]:=Fx[k–1,v];
Chuù yù: chæ khaùc baøi baloâ 1 ôû choã duøng C[k] thay cho A[k]
Döôùi ñaây laø baûng Fx[k,v] tính ñöôïc trong ví duï treân:
k v 1 2 3 4 5 6 7 8 9 10 11 12 13
1 0 0 4 4 4 4 4 4 4 4 4 4 4
2 0 0 4 5 5 5 9 9 9 9 9 9 9
3 0 0 4 5 6 6 9 10 11 11 11 15 15
4 0 3 4 5 7 8 9 10 12 13 14 15 15
5 1 3 4 5 7 8 9 10 12 13 14 15 16
4.7. Baøi toaùn baloâ 3:
Ñeà baøi: Cho n loaïi haøng (n ≤ 50). Moãi moùn haøng thuoäc loaïi thöù i coù khoái
löôïng laø A[i] vaø giaù trò C[i] (soá nguyeân). Soá löôïng caùc moùn haøng cuûa moãi loaïi
khoâng haïn cheá. Caàn choïn nhöõng moùn haøng cuûa nhöõng loaïi haøng naøo ñeå boû vaøo
moät ba loâ sao toång giaù trò cuûa caùc moùn haøng ñaõ choïn laø lôùn nhaát nhöng toång khoái
löôïng cuûa chuùng khoâng vöôït quaù khoái löôïng W cho tröôùc (W ≤ 100).
Moãi loaïi haøng coù theå hoaëc khoâng choïn moùn naøo, hoaëc choïn 1 moùn, hoaëc
choïn nhieàu moùn.
Quy hoaïch ñoäng 9 Traàn Quang Quaù
Input:
nW
A[1] C[1]
A[2] C[2]
…
A[n] C[n]
Ví duï:
5 13
3 4
4 5
5 6
2 3
1 1
OutPut:
Toång giaù trò cuûa caùc moùn haøng boû vaøo ba loâ.
Soá löôïng cuûa caùc loaïi haøng ñaõ choïn.
Trong ví duï treân:
Toång giaù trò cuûa caùc moùn haøng boû vaøo ba loâ: 19
Caùc moùn ñöôïc choïn:
Choïn 1 moùn haøng loaïi 1, moãi moùn coù khoái löôïng laø 3 vaø giaù trò laø 4
Choïn 5 moùn haøng loaïi 4, moãi moùn coù khoái löôïng laø 2 vaø giaù trò laø 3
Höôùng giaûi:
1) Toå chöùc döõ lieäu:
Fx[k, v] laø toång giaù trò cuûa caùc moùn haøng boû vaøo ba loâ khi coù k loaïi haøng
ñaàu tieân ñeå choïn vaø khoái löôïng toái ña cuûa ba loâ laø v.
Vôùi k ∈ [1, n], v ∈ [1, W].
X[k, v] laø soá löôïng caùc moùn haøng loaïi k ñöôïc choïn khi khoái löôïng toái ña cuûa
ba loâ laø v.
2) Giaûi thuaät taïo baûng:
* Tröôøng hôïp ñôn giaûn chæ coù 1 moùn ñeå choïn: Ta tính Fx[1, v] vôùi moïi v:
X[1, v] = v div A[1]
Fx[1, v] = X[1, v] * C[1]
* Giaû söû ta ñaõ tính ñöôïc Fx[k–1 , v ] ñeán doøng k–1, vôùi moïi v ∈ [1, W].
Khi coù theâm loaïi thöù k ñeå choïn, ta caàn tính Fx[k , v] ôû doøng k, vôùi moïi v∈[1,W]
Neáu ta choïn xk moùn haøng loaïi k, thì khoái löôïng coøn laïi cuûa ba loâ daønh cho
caùc loaïi haøng töø loaïi 1 ñeán loaïi k – 1 laø: u = v – xk * A[k]
Khi ñoù giaù trò cuûa ba loâ laø: Fx[k, v]= Fx[k–1,u] + xk * C[k]
Vôùi xk thay ñoåi töø 0 ñeán yk, ta choïn giaù trò lôùn nhaát vaø löu vaøo Fx[k, v].
Trong ñoù yk = v div A[k] laø soá löôïng lôùn nhaát caùc moùn haøng loaïi k coù theå ñöôïc
choïn boû vaøo ba loâ, khi khoái löôïng toái ña cuûa ba loâ laø v.
Quy hoaïch ñoäng 10 Traàn Quang Quaù
Toùm laïi: coâng thöùc ñeä quy laø:
Fx[k,v] = Max(Fx[k-1, v – xk * A[k]] + xk * C[k])
Max xeùt vôùi xk thay ñoåi töø 0 ñeán v div A[k], vaø v – xk * A[k] > 0
Döôùi ñaây laø baûng Fx[k,v] vaø X[k, v] tính ñöôïc trong ví duï treân. Baûng maøu
xaùm laø X[k, v]:
k v 1 2 3 4 5 6 7 8 9 10 11 12 13
1 0 0 0 0 4 1 4 1 4 1 8 2 8 2 8 2 12 3 12 3 12 3 16 4 16 4
2 0 0 0 0 4 0 4 0 5 1 8 0 9 1 9 1 12 0 13 1 14 2 16 0 17 1
3 0 0 0 0 4 0 4 0 5 0 8 0 9 0 10 1 12 0 13 0 14 0 16 0 17 0
4 0 0 0 0 4 0 4 0 7 1 8 0 10 2 11 1 13 3 14 2 16 4 17 3 19 5
5 0 0 1 1 4 0 5 1 7 0 8 0 10 0 11 0 13 0 14 0 16 0 17 0 19 0
Procedure TaoBang;
Var xk, yk, k: Byte;
FMax, XMax, v : Word;
Begin
For v:= 1 To W Do
begin
X[1, v] := v div A[1];
F[1, v] := X[1, v] * C[1];
end;
For k:= 2 To n Do
For v:= 1 To W Do
begin
FMax := F[k-1, v] ;
XMax := 0;
yk := v div A[k];
For xk:= 1 To yk Do
If (v - xk * A[k] > 0) and
F[k-1, v - xk * A[k]] + xk * C[k] > FMax) Then
begin
FMax := F[k-1, v - xk * A[k]] + xk * C[k];
XMax:= xk;
end;
F[k, v] := FMax;
X[k, v] := XMax;
end;
End;
3) Giaûi thuaät tra baûng:
Fx[n, W] laø giaù trò lôùn nhaát cuûa ba loâ.
Baét ñaàu töø X[n, W] laø soá moùn haøng loaïi k ñöôïc choïn.
Tính v = W – X[n, W]* A[n].
Tìm ñeán oâ [n – 1, v ] ta tìm ñöôïc X[n – 1, v]. Cöù tieáp tuïc ta tìm ñöôïc X[1, v].
Chuù yù: khi tra baûng, ta khoâng duøng maûng Fx[k, v], neân ta coù theå caûi tieán:
duøng 2 maûng moät chieàu thay cho maûng hai chieàu Fx.
Quy hoaïch ñoäng 11 Traàn Quang Quaù
4.8. Baøi toaùn ñoåi tieàn:
Ñeà baøi: Cho n loaïi tôø giaáy baïc. Tôø giaáy baïc thöù i coù meänh giaù A[i]. Soá tôø
moãi loaïi khoâng giôùi haïn. Caàn chi traû cho khaùch haøng soá tieàn M ñoàng. Haõy cho
bieát moãi loaïi tieàn caàn bao nhieâu tôø sao cho toång soá tôø laø ít nhaát. Neáu khoâng ñoåi
ñöôïc, thì thoâng baùo “KHONG DOI DUOC”. N < 50; A[i] < 256; M < 10000
Input: nM
A[1] A[2] … A[n]
Ví duï: 3 18
3 10 12
Output: Toång soá tôø phaûi traû.
Soá tôø moãi loaïi.
Caùch giaûi thöù nhaát: Töông töï baøi ba loâ 3
Goïi Fx[i, j ] laø soá tôø ít nhaát ñöôïc duøng ñeå traû soá tieàn j ñoàng khi coù i loaïi tieàn
töø loaïi 1 ñeán loaïi i. Vôùi i = 1 .. n; j = 1 .. M.
X[i, j] laø soá tôø giaáy baïc loaïi thöù i ñöôïc duøng chi traû soá tieàn j ñoàng.
* Tröôøng hôïp ñôn giaûn chæ coù 1 loaïi tieàn ñeå choïn: Ta tính Fx[1, j] vôùi moïi j
j div A[1] neáu j mod A[1] = 0
{
Fx[1, j] =
neáu j mod A[1] ≠ 0 (khoâng ñoåi ñöôïc)
∞
* Giaû söû ta ñaõ tính ñöôïc Fx[i–1 , j ] ñeán doøng i–1, vôùi moïi j ∈ [1, M]. Khi
coù theâm loaïi tieàn thöù i ñeå choïn, ta caàn tính Fx[i , j] ôû doøng i, vôùi moïi j∈[1, M]
Neáu ta choïn k tôø loaïi i, thì soá tieàn coøn laïi daønh cho caùc loaïi tieàn khaùc töø loaïi
1 ñeán loaïi i – 1 laø: u = j – k * A[k]
Khi ñoù toång soá tôø laø: Fx[i, j]= Fx[i–1,u] + k
Vôùi k thay ñoåi töø 0 ñeán kMax, ta choïn giaù trò nhoû nhaát vaø löu vaøo Fx[i, j].
Trong ñoù kMax = j div A[k] laø soá tôø nhieàu nhaát cuûa loaïi tieàn i ñeå ñoåi soá tieàn j.
Toùm laïi: coâng thöùc ñeä quy laø:
Fx[i,j] = Min(Fx[i-1, j – k * A[i]] + k)
Min xeùt vôùi k thay ñoåi töø 0 ñeán j div A[i], vaø j – k * A[i] > 0
Caùch giaûi thöù hai:
Goïi Fx[i] laø soá tôø ít nhaát ñöôïc duøng ñeå ñoåi soá tieàn i. Vôùi i = 1 .. M.
Vôùi quy öôùc Fx[i] = ∞ (hoaëc 0) khi khoâng ñoåi ñöôïc.
X[i] laø loaïi tieàn cuoái cuøng ñöôïc duøng ñoåi soá tieàn i. (chæ löu 1 loaïi tieàn)
Giaûi thuaät taïo baûng:
Xeáp meänh giaù A[i] taêng daàn.
Khôûi gaùn Fx[i] = VoâCöïc, X[i] = 0 vôùi moïi j = 1 .. M
Gaùn Fx[0] = 0
Vôùi soá tieàn i chaïy töø 1 ñeán M, ta tính Fx[i] vaø X[i], baèng caùch:
Quy hoaïch ñoäng 12 Traàn Quang Quaù
Neáu choïn loaïi tieàn j thì soá tieàn coøn laïi laø i – A[j]
Fx[i] = Min( Fx[i – A[j]] + 1) neáu i >= A[j]
Min xeùt vôùi loaïi tieàn j chaïy töø 1 ñeán n.
X[i] = j öùng vôùi giaù trò min cuûa Fx[i]
Döôùi ñaây laø maûng Fx[i] vaø X[i] tính ñöôïc trong ví duï treân
(duøng 3 loaïi tieàn 3 ñoàng, 10 ñoàng, 12 ñoàng ñeå ñoåi soá tieàn 18 ñoàng)
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Fx[i] ∞ ∞ ∞ ∞ ∞ ∞ ∞ 31∞12∞23∞3
1 2
X[i] 0 0 0 1 0 0 1 0 0 1203203203
Procedure TaoBang;
Var i: Word;
j: Byte;
Begin
For i:= 1 to M Do Fx[i] := VoCuc; {VoâCöïc = MaxInt – 1 }
Fx[0] := 0;
FillChar(X, SizeOf(X), 0);
{ i laø soá tieàn }
For i := 1 to M Do
{j laø loaïi tieàn }
For j := n DownTo 1 Do
If i >= A[j] Then
If (Fx[i] > Fx[i - A[j]] + 1) Then
Begin
Fx[i]:= Fx[i - A[j]] + 1;
X[i] := j;
End;
End;
Quy hoaïch ñoäng 13 Traàn Quang Quaù
4.9. Phaân coâng kó sö
(Ñeà thi tuyeån sinh sau Ñaïi hoïc khoaù 1997 Ñaïi hoïc Toång hôïp Tp HCM)
Moät cô sôû phaàn meàm coù n phoøng maùy vi tính. Cô sôû naøy phaûi tuyeån choïn m
kó sö ñeå baûo trì maùy. Sau khi tham gia yù kieán cuûa caùc chuyeân gia vaø kinh nghieäm
cuûa caùc ñôn vò khaùc, ngöôøi ta hieåu raèng neáu phaân coâng i kó sö chuyeân baûo trì taïi
phoøng maùy j thì soá maùy hoûng haèng naêm phaûi thanh lí laø a[i,j]. Do haïn cheá veà thôøi
gian vaø ñieàu kieän ñi laïi chæ coù theå phaân coâng moãi kó sö baûo trì taïi moät phoøng maùy.
Baûng ví duï döôùi ñaây vôùi m = 5 (kó sö) vaø n = 3 (phoøng maùy).
Soá kó sö phoøng maùy 1 phoøng maùy 2 phoøng maùy 3
0 14 25 20
1 10 19 14
2 7 16 11
3 4 14 8
4 1 12 6
5 0 11 5
Yeâu caàu: Tìm ra phöông aùn phaân coâng moãi phoøng maùy phaân bao nhieâu kó sö
sao cho toång soá maùy phaûi thanh lí haèng naêm laø ít nhaát.
Döõ lieäu: vaøo töø file vaên baûn KiSu.inp coù 2 doøng:
doøng ñaàu goàm 2 soá nguyeân döông m, n. (m, n < 50)
•
m+1 doøng tieáp theo baûng a[i, j].
•
Keát quaû: ñöa ra file vaên baûn KiSu.out goàm 2 doøng:
Doøng ñaàu chöùa toång soá maùy (ít nhaát) phaûi thanh lí haèng naêm.
•
Doøng thö hai chöùa n soá nguyeân döông laø soá kó sö ñöôïc phaân coâng baûo trì
•
moãi phoøng maùy.
Trong ví duï treân, phaân coâng 3 kó sö cho phoøng maùy 1, 1 kó sö cho phoøng
maùy 2, vaø 1 kó sö cho phoøng maùy 3. Khi ñoù, haèng naêm soá maùy ít nhaát phaûi thanh lí
laø 37 maùy.
Ví duï:
KiSu.inp (ñoái vôùi ví duï treân) KiSu.out
53 37
14 25 20 311
10 19 14
7 16 11
4 14 8
1 12 6
0 11 5
Höôùng daãn giaûi:
Goïi F[i, j] laø soá maùy hö ít nhaát haèng naêm khi coù i kó sö ñöôïc phaân coâng baûo
trì j phoøng maùy ñaàu tieân.
Quy hoaïch ñoäng 14 Traàn Quang Quaù
4.10. Tam phaân ña giaùc:
Cho moät ña giaùc loài n ñænh. Haõy phaân ña giaùc naøy thaønh n – 2 tam giaùc
baèng n – 3 ñöôøng cheùo, sao cho toång cuûa ñoä daøi cuûa caùc ñöôøng cheùo naøy laø nhoû
nhaát. Caùc ñöôøng cheùo naøy khoâng caét nhau (chæ coù theå giao nhau ôû ñænh cuûa ña
giaùc).
Döõ lieäu: vaøo töø file vaên baûn TAMPHAN.INP coù n + 1 doøng:
• Doøng ñaàu chöùa moät soá nguyeân n laø soá ñænh cuûa ña giaùc (3 < n < 50).
• Moãi doøng trong n doøng keá tieáp chöùa hai soá thöïc laø hoaønh ñoä vaø tung
ñoä cuûa moãi ñænh cuûa ña giaùc.
Keát quaû: ñöa ra file vaên baûn TAMPHAN.OUT, goàm doøng ñaàu chöùa moät soá
thöïc (coù 4 chöõ soá thaäp phaân) laø toång nhoû nhaát cuûa ñoä daøi cuûa caùc ñöôøng cheùo.
Moãi doøng trong n – 3 doøng tieáp theo chöùa 2 soá nguyeân laø chæ soá cuûa hai ñænh cuûa
moãi ñöôøng cheùo ñöôïc choïn.
Ví duï:
TAMPHAN.INP TAMPHAN.OUT
6 17.4859
21 26
24 36
66 35
10 6
10 3
70
Höôùng daãn: Goïi Fx[i, j] laø toång ñoä daøi ngaén nhaát cuûa caùc ñöôøng cheùo khi
tam phaân ña giaùc coù i ñænh keå töø ñænh thöù j.
4.11. Traïm böu ñieän
Treân moät con ñöôøng thaúng, daøi, soá nhaø cuûa nhöõng nhaø doïc theo moät beân
ñöôøng laø soá ño ñoä daøi tính töø ñaàu con ñöôøng (soá nguyeân). Ngöôøi ta choïn ra k nhaø
laøm traïm böu ñieän.
Haõy xaùc ñònh soá nhaø cuûa k nhaø ñoù sao cho caùc nhaø coøn laïi caùch moät traïm
böu ñieän naøo ñoù laø gaàn nhaát hay toång khoaûng caùch cuûa caùc nhaø coøn laïi ñeán moät
traïm böu ñieän gaàn nhaát naøo ñoù laø nhoû nhaát.
Döõ lieäu: vaøo töø file vaên baûn BuuDien.inp goàm 2 doøng:
• Doøng ñaàu: chöùa hai soá nguyeân n vaø k ( n < 300; k < 30), vôùi n laø toång
soá nhaø treân con ñöôøng ñoù, k laø soá traïm böu ñieän.
• Doøng thöù hai laø caùc soá nhaø theo thöù töï taêng daàn.
Keát quaû: ñöa ra file vaên baûn BuuDien.out goàm 2 doøng:
• Doøng ñaàu: laø k nhaø duøng laøm traïm böu ñieän.
• Doøng thöù hai laø toång khoaûng caùch cuûa caùc nhaø coøn laïi ñeán moät traïm
böu ñieän gaàn nhaát naøo ñoù.
Ví duï:
BuuDien.inp BuuDien.out
10 5 2 7 22 44 50
1 2 3 6 7 9 11 22 44 50 9
Quy hoaïch ñoäng 15 Traàn Quang Quaù
4.12. Xaâu con chung daøi nhaát:
Cho hai xaâu kí töï s1 vaø s2. Tìm xaâu kí töï s coù nhieàu kí töï nhaát, vôùi s vöøa laø
xaâu con cuûa xaâu s1, vöøa laø xaâu con cuûa xaâu s2. (Xaâu con laø xaâu kí töï coù ñöôïc khi
boû bôùt moät soá kí töï trong xaâu cha).
Döõ lieäu: vaøo töø taäp tin vaên baûn XauChung.inp goàm hai doøng, moãi doøng laø
moät xaâu kí töï.
Keát quaû: ñöa ra taäp tin vaên baûn XauChung.out goàm 2 doøng:
Doøng ñaàu laø ñoä daøi cuûa xaâu con chung daøi nhaát.
•
Doøng thöù hai laø xaâu con chung s.
•
Ví duï:
XauChung.inp XauChung.out
luong the vinh bien hoa 9
ngo quyen dong nai ng en n a
