CHUYÊN ĐỀ
QUY HO CH Đ NGẠ Ộ
Chuyên đ : Quy ho ch đ ngề ạ ộ –THPT Cà Mau
M C L CỤ Ụ
Trang
CHUYÊN ĐỀ ............................................................................................................. 1
QUY HO CH Đ NGẠ Ộ .............................................................................................. 1
M C L CỤ Ụ ................................................................................................................. 2
CHUYÊN Đ : QUY HO CH Đ NGỀ Ạ Ộ .................................................................... 3
I. M T S KI N TH C V L P TRÌNH Đ NGỘ Ố Ế Ứ Ề Ậ Ộ ............................................. 3
II. M T S BÀI TOÁN QUY HO CH Đ NG ĐI N HÌNHỘ Ố Ạ Ộ Ể ............................ 5
Bài toán 12.1: Dãy con chung dài nh t (2) {DAYCON.PAS}ấ ................ 34
2
B i d ng HSG – môn tin h c, tr ng THPT Cà Mauồ ưỡ ọ ườ
CHUYÊN Đ : QUY HO CH Đ NGỀ Ạ Ộ
***
I. M T S KI N TH C V L P TRÌNH Đ NGỘ Ố Ế Ứ Ề Ậ Ộ
1. Ph ng pháp quy ho ch đ ngươ ạ ộ
Ph ng pháp quy ho ch đ ng cùng nguyên lý t i u đ c nhà toán h c M R.Bellmanươ ạ ộ ố ư ượ ọ ỹ
đ xu t vào nh ng năm 50 c a th k 20. Ph ng pháp này đã đ c áp d ng đ gi i hàng lo tề ấ ữ ủ ế ỷ ươ ượ ụ ể ả ạ
bài toán th c t trong các quá trình k thu t c ng ngh , t ch c s n xu t, k ho ch hoá kinhự ế ỹ ậ ộ ệ ổ ứ ả ấ ế ạ
t … Tuy nhiên c n l u ý r ng có m t s bài toán mà cách gi i b ng quy ho ch đ ng t raế ầ ư ằ ộ ố ả ằ ạ ộ ỏ
không thích h p.ợ
Trong th c t , ta th ng g p m t s bài toán t i u lo i sau: Có m t đ i l ng ự ế ườ ặ ộ ố ố ư ạ ộ ạ ượ f hình
thành trong m t quá trình g m nhi u giai đo n và ta ch quan tâm đ n k t qu cu i cùng là giáộ ồ ề ạ ỉ ế ế ả ố
tr c a ị ủ f ph i l n nh t ho c nh nh t, ta g i chung là giá tr t i u c a ả ớ ấ ặ ỏ ấ ọ ị ố ư ủ f. Giá tr c a ị ủ f phụ
thu c vào nh ng đ i l ng xu t hi n trong bài toán mà m i b giá tr c a chúng đ c g i làộ ữ ạ ượ ấ ệ ỗ ộ ị ủ ượ ọ
m t ộtr ng tháiạ c a h th ng và ph thu c vào cách th c đ t đ c giá tr ủ ệ ố ụ ộ ứ ạ ượ ị f trong t ng giai đo nừ ạ
mà m i cách t ch c đ c g i là m t ỗ ổ ứ ượ ọ ộ đi u khi nề ể . Đ i l ng ạ ượ f th ng đ c g i là ườ ượ ọ hàm m cụ
tiêu và quá trình đ t đ c giá tr t i u c a ạ ượ ị ố ư ủ f đ c g i là ượ ọ quá trình đi u khi n t i uề ể ố ư .
Bellman phát bi u nguyên lý t i u (cũng g i là ể ố ư ọ nguyên lý Bellman) mà ý t ng c b nưở ơ ả
là nh sau: “V i m i quá trình đi u khi n t i u, đ i v i tr ng thái b t đ u ư ớ ỗ ề ể ố ư ố ớ ạ ắ ầ A0, v i tr ng tháiớ ạ
A trong quá trình đó, ph n quá trình k t tr ng thái ầ ể ừ ạ A xem nh tr ng thái b t đ u cũng là t iư ạ ắ ầ ố
u”.ư
Chú ý r ng nguyên lý này đ c th a nh n mà không ch ng minh.ằ ượ ừ ậ ứ
Ph ng pháp tìm đi u khi n t i u theo nguyên lý Bellman th ng đ c g i là ươ ề ể ố ư ườ ượ ọ quy
ho ch đ ngạ ộ . Thu t ng này nói lên th c ch t c a quá trình đi u khi n là đ ng: có th trongậ ữ ự ấ ủ ề ể ộ ể
m t s b c đ u tiên l a ch n đi u khi n t i u d ng nh không t t nh ng t u chung cộ ố ướ ầ ự ọ ề ể ố ư ườ ư ố ư ự ả
quá trình l i là t t nh t.ạ ố ấ
Ta có th gi i thích ý này qua bài toán sau: Cho m t dãy ể ả ộ N s nguyên ốA1, A2,…,AN. Hãy
tìm cách xoá đi m t s ít nh t s h ng đ dãy còn l i là đ n đi u hay nói cách khác hãy ch nộ ố ấ ố ạ ể ạ ơ ệ ọ
m t s nhi u nh t các s h ng sao cho dãy B g m các s h ng đó theo trình t xu t hi n trongộ ố ề ấ ố ạ ồ ố ạ ự ấ ệ
dãy A là đ n đi u.ơ ệ
Quá trình ch n ọB đ c đi u khi n qua ượ ề ể N giai đo n đ đ t đ c m c tiêu là s l ngạ ể ạ ượ ụ ố ượ
s h ng c a dãy ố ạ ủ B là nhi u nh t, đi u khi n giai đo n ề ấ ề ể ở ạ i th hi n vi c ch n hay không ch nể ệ ệ ọ ọ
Ai vào dãy B.
Gi s dãy đã cho là 1 8 10 2 4 6 7. N u ta ch n l n l t 1, 8, 10 thì ch ch n đ c 3 sả ử ế ọ ầ ượ ỉ ọ ượ ố
h ng nh ng n u b qua 8 và 10 thì ta ch n đ c 5 s h ng 1, 2, 4, 6, 7.ạ ư ế ỏ ọ ượ ố ạ
Khi gi i m t bài toán b ng cách “chia đ tr ” chuy n vi c gi i bài toán kích th c l nả ộ ằ ể ị ể ệ ả ướ ớ
v vi c gi i nhi u bài toán cùng ki u có kích th c nh h n thì thu t toán này th ng đ cề ệ ả ề ể ướ ỏ ơ ậ ườ ượ
th hi n b ng các ch ng trình con đ quy. Khi đó, trên th c t , nhi u k t qu trung gian ph iể ệ ằ ươ ệ ự ế ề ế ả ả
tính nhi u l n.ề ầ
V y ý t ng c b n c a quy ho ch đ ng th t đ n gi n: tránh tính toán l i m i th haiậ ưở ơ ả ủ ạ ộ ậ ơ ả ạ ọ ứ
l n, mà l u gi k t qu đã tìm ki m đ c vào m t b ng làm gi thi t cho vi c tìm ki mầ ư ữ ế ả ế ượ ộ ả ả ế ệ ế
nh ng k t qu c a tr ng h p sau. Chúng ta s làm đ y d n giá tr c a b ng này b i các k tữ ế ả ủ ườ ợ ẽ ầ ầ ị ủ ả ở ế
qu c a nh ng tr ng h p tr c đã đ c gi i. K t qu cu i cùng chính là k t qu c a bàiả ủ ữ ườ ợ ướ ượ ả ế ả ố ế ả ủ
toán c n gi i. Nói cách khác ph ng pháp quy ho ch đ ng đã th hi n s c m nh c a nguyênầ ả ươ ạ ộ ể ệ ứ ạ ủ
lý chia đ tr đ n cao đ .ể ị ế ộ
Quy ho ch đ ng là k thu t thi t k bottom-up (t d i lên). Nó đ c b t đ u v iạ ộ ỹ ậ ế ế ừ ướ ượ ắ ầ ớ
nh ng tr ng h p con nh nh t (th ng là đ n gi i nh t và gi i đ c ngay). B ng cách tữ ườ ợ ỏ ấ ườ ơ ả ấ ả ượ ằ ổ
h p các k t qu đã có (ợ ế ả không ph i tính l iả ạ ) c a các tr ng h p con, s đ t đ t t i k t qu c aủ ườ ợ ẽ ạ ạ ớ ế ả ủ
tr ng h p có kích th c l n d n lên và t ng quát h n, cho đ n khi cu i cùng đ t t i l i gi iườ ợ ướ ớ ầ ổ ơ ế ố ạ ớ ờ ả
c a tr ng h p t ng quát nh t.ủ ườ ợ ổ ấ
Trong m t s tr ng h p, khi gi i m t bài toán ộ ố ườ ợ ả ộ A, tr c h t ta tìm h bài toán ướ ế ọ A(p) phụ
thu c tham s p (có th p là m t véc t ) mà ộ ố ể ộ ơ A(p0)=A v i pớ0 là tr ng thái ban đ u c a bài toán ạ ầ ủ A.
Sau đó tìm cách gi i h bài toán ả ọ A(p) v i tham s p b ng cách áp d ng nguyên lý t i u c aớ ố ằ ụ ố ư ủ
Bellman. Cu i cùng cho p=pố0 s nh n đ c k t qu c a bài toán ẽ ậ ượ ế ả ủ A ban đ u.ầ
2. Các b c th c hi n quy ho ch đ ng ướ ự ệ ạ ộ
3
Chuyên đ : Quy ho ch đ ngề ạ ộ –THPT Cà Mau
B cướ 1: L p h th cậ ệ ứ
D a vào nguyên lý t i u tìm cách chia quá trình gi i bài toán thành t ng giai đo n, sauự ố ư ả ừ ạ
đó tìm h th c bi u di n t ng quan quy t đ nh c a b c đang x lý v i các b c đã x lýệ ứ ể ễ ươ ế ị ủ ướ ử ớ ướ ử
tr c đó. Ho c tìm cách phân rã bài toán thành các “bài toán con” t ng t có kích th c nhướ ặ ươ ự ướ ỏ
h n, tìm h th c nêu quan h gi a k t qu bài toán kích th c đã cho v i k t qu c a các “bàiơ ệ ứ ệ ữ ế ả ướ ớ ế ả ủ
toán con” cùng ki u có kích th c nh h n c a nó nh m xây d ng ph ng trình truy toánể ướ ỏ ơ ủ ằ ự ươ
(d ng hàm ho c th t c đ quy).ạ ặ ủ ụ ệ
V m t cách xây d ng ph ng trình truy toán:ề ộ ự ươ
Ta chia vi c gi i bài toán thành n giai đo n. M i giai đo n i có tr ng thái ban đ u là t(i)ệ ả ạ ỗ ạ ạ ầ
và ch u tác đ ng đi u khi n d(i) s bi n thành tr ng thái ti p theo t(i+1) c a giai đo n i+1ị ộ ề ể ẽ ế ạ ế ủ ạ
(i=1,2,…,n-1). Theo nguyên lý t i u c a Bellman thì vi c t i u giai đo n cu i cùng khôngố ư ủ ệ ố ư ạ ố
làm nh h ng đ n k t qu toàn bài toán. V i tr ng thái ban đ u là t(n) sau khi làm giai đo n nả ưở ế ế ả ớ ạ ầ ạ
t t nh t ta có tr ng thái ban đ u c a giai đo n n-1 là t(n-1) và tác đ ng đi u khi n c a giaiố ấ ạ ầ ủ ạ ộ ề ể ủ
đo n n-1 là d(n-1), có th ti p t c xét đ n giai đo n n-1. Sau khi t i u giai đo n n-1 ta l i cóạ ể ế ụ ế ạ ố ư ạ ạ
t(n-2) và d(n-2) và l i có th t i u giai đo n n-2 … cho đ n khi các giai đo n t n gi m đ n 1ạ ể ố ư ạ ế ạ ừ ả ế
đ c t i u thì coi nh hoàn thành bài toán. G i giá tr t i u c a bài toán tính đ n giai đo n kượ ố ư ư ọ ị ố ư ủ ế ạ
là Fk giá tr t i u c a bài toán tính riêng giai đo n k là ị ố ư ủ ở ạ Gk thì
Fk = Fk-1 + Gk
Hay là:
(*) }))1(())(),(({G))((
1k
)(
1
−+=
−
∀
ktFkdktaxmktF
k
kd
B cướ 2: T ch c d li u và ch ng trìnhổ ứ ữ ệ ươ
T ch c d li u sao cho đ t các yêu c u sau:ổ ứ ữ ệ ạ ầ
D li u đ c tính toán d n theo các b c.ữ ệ ượ ầ ướ
D li u đ c l u tr đ gi m l ng tính toán l p l i.ữ ệ ượ ư ữ ể ả ượ ặ ạ
Kích th c mi n nh dành cho l u tr d li u càng nh càng t t, ki u d li uướ ề ớ ư ữ ữ ệ ỏ ố ể ữ ệ
đ c ch n phù h p, nên ch n đ n gi n d truy c p.ượ ọ ợ ọ ơ ả ễ ậ
C thụ ể
•Các giá tr c a ị ủ Fk th ng đ c l u tr trong m t b ng (m ng m t chi u ho c hai,ườ ượ ư ữ ộ ả ả ộ ề ặ
ba, v.v… chi u).ề
•C n l u ý kh i tr các giá tr ban đ u c a b ng cho thích h p, đó là các k t qu c aầ ư ở ị ị ầ ủ ả ợ ế ả ủ
các bài toán con có kích c nh nh t c a bài toán đang gi i:ỡ ỏ ấ ủ ả
}))0(())1(),1(({G))1(( 01
)1(
1tFdtaxmtF
d
+=
∀
•D a vào công th c, ph ng trình truy toán (*) và các giá tr đã có trong b ng đ tìmự ứ ươ ị ả ể
d n các giá tr còn l i c a b ng.ầ ị ạ ủ ả
•Ngoài ra còn c n m ng l u tr nghi m t ng ng v i các giá tr t i u trong t ngầ ả ư ữ ệ ươ ứ ớ ị ố ư ừ
gian đo n.ạ
•D a vào b ng l u tr nghi m và b ng giá tr t i u trong t ng giai đo n đã xâyự ả ư ữ ệ ả ị ố ư ừ ạ
d ng, tìm ra k t qu bài toán.ự ế ả
B cướ 3: Làm t tố
Làm t t thu t toán b ng cách thu g n h th c (*) và gi m kích th c mi n nh .ố ậ ằ ọ ệ ứ ả ướ ề ớ
Th ng tìm cách dùng m ng m t chi u thay cho m ng hai chi u n u giá tr m t dòng (ho cườ ả ộ ề ả ề ế ị ộ ặ
c t) c a m ng hai chi u ch ph thu c m t dòng (ho c c t) k tr c.ộ ủ ả ề ỉ ụ ộ ộ ặ ộ ề ướ
Trong m t s tr ng h p có th thay m ng hai chi u v i các giá tr ph n t ch nh nộ ố ườ ợ ể ả ề ớ ị ầ ử ỉ ậ
giá tr 0, 1 b i m ng hai chi u m i b ng cách dùng k thu t qu n lý bit.ị ở ả ề ớ ằ ỹ ậ ả
3. H n ch c a quy ho ch đ ngạ ế ủ ạ ộ
•Vi c tìm công th c, ph ng trình truy toán ho c tìm cách phân rã bài toán nhi u khiệ ứ ươ ặ ề
đòi h i s phân tích t ng h p r t công phu,d sai sót, khó nh n ra nh th nào là thích h p, đòiỏ ự ổ ợ ấ ễ ậ ư ế ợ
h i nhi u th i gian suy nghĩ. Đ ng th i không ph i lúc nào k t h p l i gi i c a các bài toánỏ ề ờ ồ ờ ả ế ợ ờ ả ủ
con cũng cho k t qu c a bài toán l n h n.ế ả ủ ớ ơ
•Khi b ng l u tr đòi h i m ng hai, ba chi u … thì khó có th x lý d li u v i kíchả ư ữ ỏ ả ề ể ử ữ ệ ớ
c m i chi u l n hàng trăm.ỡ ỗ ề ớ
•Có nh ng bài toán không th gi i đ c b ng quy ho ch đ ng.ữ ể ả ượ ằ ạ ộ
4
B i d ng HSG – môn tin h c, tr ng THPT Cà Mauồ ưỡ ọ ườ
II. M T S BÀI TOÁN QUY HO CH Đ NG ĐIỘ Ố Ạ Ộ ỂN HÌNH
BÀI TOÁN 1: Đ ng điườ
Cho b ng kích th c 3 x N (1<nả ướ ≤100). Trong m i ô có ghi m t s 1 ho c 0. B ng cácỗ ộ ố ặ ằ
phép di chuy n U, D, L, R ng i ta đi t ô trên trái c aể ườ ừ ủ
băng t i ô b t kỳ bên ph i nh t c a băng (c t th n).ớ ấ ả ấ ủ ộ ứ
Không đ c đi l i vào ô đã đi qua. Đ ng đi đ c đánhượ ạ ườ ượ
giá b ng giá tr S. Ban đ u S nh n giá tr ghi ô trên trái.ằ ị ầ ậ ị ở
Sau m i b c, giá tr c a S tăng lên g p đôi và c ng v iỗ ướ ị ủ ấ ộ ớ
n i dung c a ô m i đ n. Hãy tìm đ ng đi t ng ngộ ủ ớ ế ườ ươ ứ
v i S l n nh t. Hình bên trên t ng ng v i N=5 và đ ng đi c n tìm làớ ớ ấ ươ ứ ớ ườ ầ
RDLDRRRRULLURR.
D li u:ữ ệ Vào t file văn b n BANK.INPừ ả
•Dòng đ u tiên ch a s nguyên Nầ ứ ố
•Ba dòng sau ch a 3 xâu các ký t 0,1 xác đ nh giá tr ghi trong các ô, li t kê t trái sangứ ự ị ị ệ ừ
ph i, t trên xu ng d i.ả ừ ố ướ
K t qu :ế ả Đ a ra file BANK.OUT m t s nguyên h th p phân là giá tr l n nh t tìm đ c c aư ộ ố ệ ậ ị ớ ấ ượ ủ
S
Ví d :ụ
BANK.INP BANK.OUT
5
00011
01100
00011
RDLDRRRRULLURR
CH NG TRÌNHƯƠ
{$A+,B-,D+,E+,F-,G-,I+,L+,N+,O-,P-,Q-,R-,S+,T-,V+,X+}
{$M 16384,0,655360}
uses crt;
const
tfi = 'BANK.INP';
tfo = 'BANK.OUT';
NN = 100;
maxN = 100;
maxV = 2*(maxN+1);
maxS = 100;
type
SoNguyen=string[maxS];
var
a: array[1..3,1..maxN] of byte;
n: integer;
fi,fo: text;
CS,TT: array[1..maxV] of integer;
sTT: integer;
Tr: array[1..maxV] of integer;
S : array[1..maxV] of SoNguyen;
x: array[1..maxV] of integer;
slx: integer;
Max: SoNguyen;
AmMot,zero: SoNguyen;
procedure Sinhdl;
var ch: char;
i,j: integer;
5
0 0 0 1 1
0 1 1 0 0
0 0 0 1 1