intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Chuyên đề tin học - Lý thuyết quy hoạch động

Chia sẻ: Trần Bảo Quyên Quyên | Ngày: | Loại File: PDF | Số trang:15

Thêm vào BST
Báo xấu
759
lượt xem 210
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ả.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chuyên đề tin học - Lý thuyết quy hoạch động

  1. 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. •
  2. 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
  3. 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]
  4. 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;
  5. 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;
  6. 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.
  7. 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]
  8. 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.
  9. 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.
  10. 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.
  11. 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:
  12. 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;
  13. 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.
  14. 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
  15. 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2