Nhêi nãi ®Çu :
Quy ho¹ch ®éng lµ mét ph¬ng ph¸p h÷u hiÖu ®Ó gi¶i quyÕt mét bµi to¸n tèi u.
Nh÷ng bµi gi¶i b»ng QH§ ®Òu cho kÕt qu¶ tèt vÒ c¶ ®¸p sè lÉn thêi gian. Nhng ®Ó
ph¸t hiÖn ra vµ cµi ®Æt tèt mét bµi quy ho¹ch ®éng lµ rÊt khã kh¨n. Thêng th×
chóng ta hay tiÕp cËn víi nh÷ng bµi to¸n QH§ mµ ®äc lªn ®· cã ngay d¹ng hay
ph¬ng ph¸p gi¶i, nhng nh vËy lµ cha ®ñ bëi lÏ QH§ kh«ng dõng l¹i ë ®ã. Chóng
ta chØ cã thÓ gi¸c ngé t tëng ®Ó gi¶i mét bµi QH§ chø chóng ta kh«ng thÓ häc hÕt
®îc toµn bé mäi ph¬ng ph¸p quy ho¹ch. tËp bµi nµy còng vËy, cã lÏ nã còng chØ
cho ta biÕt vµ h×nh dung nho nhá vÒ mét sè phu¬ng ph¸p QH§ vµ nh÷ng kinh
nghiÖm khi lµm mét bµi to¸n quy ho¹ch mµ t«i rót ra qua qu¸ tr×nh häc tËp và
gi¶ng d¹y. TËp QH§ nµy gåm c¸c phÇn :
PhÇn 1: Mét sè kinh nghiÖm khi lµm QH§
PhÇn 2: Mét sè bµi to¸n QH§ c¬ b¶n
PhÇn 3: C¸c bµi luyÖn vÒ QH§
PhÇn 4: Híng dÉn gi¶i bµi luyÖn QH§
C¸c bµi tËp mét sè thuéc qu¸ tr×nh häc tËp gi¶ng d¹y cña t«i vµ mét sè tuyÓn chän
tõ mét sè s¸ch, t¹p chÝ tin häc. Ch¾c ch¾n r»ng tËp bµi nµy kh«ng thÓ hoµn thiÖn
vµ kh«ng tr¸nh khái sai sãt, xin ®îc tiÕp thu ý kiÕn ®ãng gãp cña c¸c thÇy, c¸c c«.
PhÇn 1 : mét sè kinh nghiÖm khi lµm quy ho¹ch ®éng
QH§ lµ mét ph¬ng ph¸p m¹nh ®Ó gi¶i c¸c bµi to¸n trong tin häc. QH§ ®ßi hái mét kh¶
n¨ng nh×n nhËn vµ ph©n tÝch chi tiÕt mét bµi to¸n. §Ó cã ®îc nhiÒu kinh nghiÖm gi¶i
QH§ th× kh«ng mét c¸ch nµo kh¸c lµ ta ph¶i tiÕp cËn víi cµng nhiÒu cµng tèt nh÷ng bµi
to¸n QH§. vµ theo t«i th× khu«n mÉu chung ®Ó lµm quy ho¹ch ®éng gåm ba bíc :
* LËp hÖ thøc : dùa vµo nguyªn lÝ tèi u ®Ó chia bµi to¸n thµnh giai ®o¹n lµm viÖc. Sau ®ã
t×m hÖ thøc biÓu diÔn quan hÖ gi÷a c¸c bíc ®ang xö lÝ víi c¸c bíc ®· xö lÝ tríc ®ã hoÆc
1
t×m c¸ch ph©n r· thµnh nh÷ng bµi to¸n con nhá h¬n vµ tõ ®ã x©y dùng ®îc ph¬ng tr×nh
truy to¸n(d¹ng hµm hoÆc thñ tôc ®Ö quy)
* Tæ chøc d÷ liÖu vµ ch¬ng tr×nh : tæ chøc d÷ liÖu sao cho ®¹t yªu cÇu sau:
+ d÷ liÖu ®îc tÝnh to¸n dÇn theo tõng bíc
+ d÷ liÖu ®îc lu tr÷ dÓ gi¶m lîng tÝnh to¸n lÆp l¹i
+ kÝch thíc miÒn nhí dµnh cho lu tr÷ d÷ liÖu cµng nhá cµng tèt, kiÓu d÷ liÖu ®îc
chän ph¶i phï hîp dÔ truy cËp
* Lµm tèt : lµm tèt b»ng c¸ch thu hÑp hÖ thøc vµ gi¶m kh«ng gian nhí cÇn sö dông.
Tuy lÝ thuyÕt quy ho¹ch ®éng rÊt ®¬n gi¶n nh vËy nhng viÖc ¸p dông nã vµo mét bµi to¸n lµ
kh«ng hÒ dÔ dµng bëi lÏ víi mçi bµi to¸n ®ßi hái ta ph¶i thiÕt lËp ®uîc mét ph¬ng tr×nh truy
to¸n kh¸c nhau, chÝnh ph¬ng tr×nh truy to¸n ®ã thÓ hiÖn kh¶ n¨ng t duy s¸ng t¹o cña mçi ngêi. Nãi chung quy ho¹ch ®éng lµ mét ph¬ng ph¸p ®ßi hái ta ph¶i nh×n nhËn bµi to¸n cùc k×
tinh tÕ vµ biÕt c¸ch tæ chøc d÷ liÖu hîp lÝ céng víi mét phong c¸ch lËp tr×nh tèt, kh«ng lµm
®îc vËy th× viÖc gi¶i mét bµi quy ho¹ch ®éng phøc t¹p lµ v« cïng khã kh¨n. Tríc khi lµm
quy ho¹ch ®éng h·y suy nghÜ thËt kÜ ®Ó t×m ra vµ x©y dùng c«ng trøc truy håi cho thËt
chÝnh x¸c vµ ph¶i v¹ch ra ®îc ®êng lèi lµm viÖc ®óng ®¾n vµ th«ng suèt, cã vËy ta míi b¾t
tay vµo lËp tr×nh, nÕu kh«ng chØ cÇn mét lçi nhá trong qu¸ tr×nh lËp tr×nh sÏ khiÕn ta ph¶i t
duy l¹i toµn bé qu¸ tr×nh lµm viÖc vµ còng cã thÓ b¹n ph¶i quay l¹i vÞ trÝ xuÊt ph¸t vµ nh vËy
®¬ng nhiªn b¹n sÏ mÊt rÊt nhiÒu thêi gian.
Cßn ®©y lµ c¸ch nh×n nhËn ph¬ng ph¸p quy ho¹ch ®éng cña b¹n Ph¹m H¶i Minh
Quy hoạch động là một phương pháp rất hay và mạnh của tin học. Nhưng để giải được
các bài toán bằng phương pháp quy hoạch động thật chẳng dễ dàng chút nào. Chủ yếu
học sinh hiện nay sử dụng quy hoạch động theo kiểu làm từng bài cho nhớ mẫu và áp
dụng vào những bài có dạng tương tự.
Qua quá trình học tập và giảng dạy tôi đã tự rút ra cho mình một số kinh nghiệm về cách
giải các bài toán bằng quy hoạch động, xin đưa ra để mọi người cùng tham khảo và góp
ý.
1. Lí thuyết:
Phương pháp quy hoạch động gồm 6 bước:
- Bước 1: Chia nhỏ bài toán
Lập vectơ P có các thành phần x1,x2,..,xn. Mỗi vectơ P ứng với một bài toán con của bài
toán. Ban đầu ta xây dựng P với 1 thành phần duy nhất.
- Bước 2: Lập hệ thức quy hoạch động
Xây dựng hàm f(P) là hàm tối ưu của vectơ P (hay hàm tối ưu cho mỗi bài toán con)
f(P) = g(f(P1),f(P2),..,f(Pn))
g có thể là hàm Max,Min hoặc tổng tuỳ yêu cầu của bài toán là tìm Max,Min hay tính
tổng.
P gọi là vectơ cha
P1,P2,P3,..,Pn gọi là vectơ con
- Bước 3: Kiểm tra
Nếu không xây dựng được hàm f thì thêm tiếp hoặc bỏ đi từng thành phần của vectơ P
rồi quay lại bước 2. Nếu được thì làm tiếp bước 4.
2
- Bước 4: Tối ưu hoá hệ thức
Tối ưu vectơ P bằng cách xét từng thành phần x của vectơ P:
Chọn vectơ PBest trong P1,P2,P3,..Pn chỉ khác nhau thành phần x sao cho có thể đưa
PBest vào thay P1,P2,P3..,Pn trong hàm g mà không làm thay đổi giá trị của hàm g thì có
thể đơn giản thành phần x của vectơ P.
- Bước 5: Chọn kiểu quy hoạch động
+ Kiểu 1: Nếu các thành phần của vectơ con P1 luôn ≤ hay ≥ các thành phần của vectơ
cha P thì ta có thể dùng các vòng lặp for lồng nhau để cài đặt.
+ Kiểu 2: Nếu vectơ P và vectơ P1 luôn có mối quan hệ cha con một chiều thì ta có thể
dùng phương pháp đệ quy có nhớ để cài đặt.
+ Kiểu 3: Nếu vectơ P và vectơ P1 luôn có mối quan hệ cha con hai chiều nhưng không
rõ đâu là vectơ cha , đâu là vectơ con vì còn phụ thuộc vào từng bài toán thì ta có thể
dùng phương pháp repeat.. until để cài đặt.
- Bước 6: Tối ưu hoá bộ nhớ (chỉ dùng cho cài đặt kiểu 1)
Đơn giản vectơ P bằng cách xét từng thành phần x của vectơ P:
Nếu f(P(..,x,.. ))=g(f(P1(..,x1,..)),f(P2(..,x2,..)),..,f(Pn(..,xn,..)))
và x-x1, x-x2,.., x-xn≤T nào đó thì ta chỉ cần đưa vòng lặp của x lên đầu tiên và bỏ x ra
khỏi vectơ P và lưu T+1 vectơ P.
Tãm l¹i dï nãi thÓ nµo th× ph¬ng ph¸p nµy chñ yÕu ®ßi hái kh¶ n¨ng thiÕt lËp mét ph¬ng
¸n chia nhá vµ ph©n r· bµi to¸n cho tíi khi vÊn ®Ò cßn l¹i ta cã thÓ gi¶i quyÕt ngay tøc th×.
PhÇn 2 : Mét sè bµi to¸n quy hoach ®éng c¬ b¶n:
Bµi1 : D·y con t¨ng dµi nhÊt : Cho d·y sè nguyªn n phÇn tö, h·y t×m d·y con t¨ng chÆt dµi nhÊt cña
d·y ®· cho ( c¸c phÇn tö cña d·y con cã thÓ kh«ng liªn tiÕp nhau).
D÷ liÖu vµo file DCT.INP:
- dßng ®Çu tiªn ghi sè n (1<=n<=10000)
- dßng thø i trong sè n dong tiÕp theo mçi dßng ghi sè ai (0<=ai<=30000)
KÕt qu¶ ra file DCT.OUT dßng ®Çu tiªn ghi m lµ sè lîng phÇn tö cña d·y con t¨ng dµi nhÊt t×m ®îc. m dong sau mçi dßng ghi mét phÇn tö cña d·y con t¨ng t×m ®îc.
VÝ dô
DCT.INP DCT.OUT
6
4
1
1
5
2
2
3
8
7
3
7
3
Gi¶i thuËt : Gäi d·y ban ®Çu lµ a1,a2,...an ®Æt D[i] lµ ®é dµi lín nhÊt cña d·y con t×m ®îc tõ d·y b¾t
®Çu tõ vÞ trÝ a1 kÕt thóc ë ai. nh vËy ta cã hÖ thøc quy ho¹ch ®éng : D[i]= Max(D[j]+1) (víi
0<=j<=i-1 vµ D[i]>D[j] )
D[0]=0; a[0]= -maxint;
Ban ®Çu ta khëi t¹o m¶ng D toµn c¸c gi¸ trÞ 0. KÕt qu¶ t×m ®îc lµ Max(D[i] víi 1<=i<=n). §Ó truy
vÕt vµ in ra d·y con t¨ng dµi nhÊt ta dïng m¶ng Truoc víi Truoc[i] lµ vÞ trÝ cña phÇn tö truíc phÇn
tö i trong d·y con tèi u ®Õn vÞ trÝ i.
Ch¬ng tr×nh :
Uses crt;
Const infile
= 'DCT.INP';
outfile
= 'DCT.OUT';
maxn
= 10000;
Type M1
Var
= Array [0..Maxn] of integer;
a,d,Tr
: M1;
n,m
: integer;
f,g
: text;
procedure DocDl;
var i:integer;
begin
Assign(f,infile);
Reset(f);
Readln(f,n);
For i:=1 to n do
Readln(f,a[i]);
Close(f);
end;
Procedure ChuanBi;
begin
fillchar(D,sizeof(D),0);
fillchar(Tr,sizeof(Tr),0);
A[0]:=-maxint;
end;
Procedure XuLi;
var i,j:integer;
begin
For i:=1 to n do
For j:=i-1 downto 0 do
if (a[i]>a[j]) and (D[i]
0 do
begin
d[t]:=a[v];
inc(t);
v:=Tr[v];
end;
Writeln(g,max);
for i:=max downto 1 do
Writeln(g,D[i]);
Close(g);
4
end;
Begin
Clrscr;
DocDl;
ChuanBi;
XuLi;
Ghikq;
End.
Nh vËy víi ch¬ng tr×nh trªn ta ®· t×m ®îc d·y con t¨ng víi m· phÇn tö vµ lu vµo m¶ng D
trong thñ tôc ghikq, lµm nh vËy lµ tu©n thñ ®óng gi¶i thuËt ®Ò ra ë trªn nhng lµm vËy lµ cha
h¼n tèt. §Ó lµm tèt ta cÇn t×m ngîc l¹i tõ n--->1 ®Ó t×m d·y con gi¶m nh vËy ta kh«ng cÇn lu
vµo m¶ng D trong thñ tôc ghikq n÷a mµ ta cã thÓ in ra ngay kÕt qu¶ lµ d·y con t¨ng trong
thñ tôc ghikq. Ta t¹o hai cËn min vµ max ë hai ®Çu d·y lµ vÞ trÝ a[0] vµ vÞ trÝ a[n+1] nh vËy
kÕt qu¶ t×m ra ngay tai vÞ trÝ 0. Ch¬ng tr×nh ®· ®îc c¶i tiÕn nh sau :
Uses crt;
Const infile
= 'DCT.INP';
outfile
= 'DCT.OUT';
maxn
= 10000;
Type M1
Var
= Array [0..Maxn+1] of integer;
a,d,Tr
: M1;
n,m
: integer;
f,g
: text;
procedure DocDl;
var i:integer;
begin
Assign(f,infile);
Reset(f);
Readln(f,n);
For i:=1 to n do
Readln(f,a[i]);
Close(f);
end;
Procedure ChuanBi;
begin
fillchar(D,sizeof(D),0);
fillchar(Tr,sizeof(Tr),0);
A[0]:=-maxint;
A[n+1]:=maxint;
end;
Procedure XuLi;
var i,j:integer;
begin
For i:=n downto 0 do
For j:=i+1 to n+1 do
if (a[i]n+1 do
begin
Writeln(g,a[v]);
v:=Tr[v];
end;
Close(g);
end;
Begin
Clrscr;
DocDl;
ChuanBi;
XuLi;
5
Ghikq;
End.
Bµi 2 : XÕp va ly(A)
Mét va ly cã thÓ chøa W ®¬n vÞ träng lîng.cã n ®å vËt mçi vËt cã träng lîng A[i] vµ cã gi¸ trÞ C[i]
hái lªn chän mçi lo¹i ®å vËt bao nhiªu ®Î xÕp vµo valy sao cho tæng gi¸ trÞ cña valy lµ lín nhÊt
D÷ liÖu vµo file valy.inp dong ®Çu tiªn lµ sè N vµ W, dßng thø i trong sè N dßng tiÕp theo mçi dßng
ghi hai sè A[i] vµ C[i]
KÕt qu¶ ra : file valy.out theo quy c¸ch sau
dßng ®Çu tiªn lµ tæng gi¸ trÞ lín nhÊt t×m ®îc cña valy
c¸c dßng tiÕp theo mçi dßng ghi hai sè i (lµ sè hiÖu vËt ®îc chän) x (lµ sè lîng chän vËt i)
VÝ dô
valy.inp
valy.out
4 10
108
5 4
2 2
1 9
3 1
8 90
2 16
híng dÉn : dïng m¶ng mét chiÒu gäi D[i] lµ tæng gi¸ trÞ lín nhÊt khi thÓ tÝch lµ i, nh vËy
D[i]=Max(D[i-A[j]] + C[j]) víi mäi 1<=j<=n 1<=i<=W
kÕt qu¶ lµ gi¸ trÞ lín nhÊt trong m¶ng D ta x©y dùng mét m¶ng chän víi Chon[i] 1<=i<=W lµ gi¸ trÞ tèi u
trong ph¬ng ¸n chän ë i vµ vËt ®îc chän cuèi cïng lµ Chon[i] Ch¬ng Tr×nh nh sau:
uses crt;
const
infile
outfile
maxn
maxW
= 'valy.inp';
= 'valy.out';
= 100;
= 5000;
Type
m1
m2
m3
= array [1..maxN] of integer;
= array [0..maxW] of longint;
= array [0..maxW] of integer;
Var
A,C,Sl
: m1;
D
: m2;
Chon
: m3;
N,W
: Integer;
Max
: Longint;
f,g
: Text;
Procedure NhapDl;
var i:integer;
begin
Assign(f,infile);
Reset(f);
Readln(f,N,W);
for i:=1 to n do
Readln(f,A[i],C[i]);
Close(f);
end;
Procedure ChuanBi;
begin
fillchar(D,sizeof(D),0);
fillchar(Chon,sizeof(Chon),0);
end;
Procedure XuLi;
var i,j:integer;
begin
for i:=1 to W do
for j:=1 to n do
if i>=A[j] then
if D[i]0 do
begin
inc(Sl[Chon[v]]);
V:=V-A[Chon[v]];
end;
end;
Procedure GhiKQ;
var i:integer;
begin
Assign(g,outfile);
Rewrite(g);
Writeln(g,Max);
for i:=1 to n do
if Sl[i]<>0 then
Writeln(g,i,' ',Sl[i]);
Close(g);
end;
Begin
Clrscr;
NhapDl;
ChuanBi;
XuLi;
XuLiKetThuc;
GhiKq;
End.
Bµi3 : xÕp valy (B)
Cho n ®å vËt mçi ®å vËt cã träng lîng A[i] vµ gi¸ trÞ C[i] sè lîng mçi lo¹i lµ mét. Yªu cÇu h·y xÕp vµo mét
valy träng lîng kh«ng qu¸ W sao cho tæng gi¸ trÞ lín nhÊt
D÷ liÖu vµo file valy.inp dong ®Çu tiªn lµ sè N vµ W, dßng thø i trong sè N dßng tiÕp theo mçi dßng
ghi hai sè A[i] vµ C[i]
KÕt qu¶ ra : file valy.out theo quy c¸ch sau
dßng ®Çu tiªn lµ tæng gi¸ trÞ lín nhÊt t×m ®îc cña valy
c¸c dßng sau mçi dßng ghi mét sè lµ sè hiÖu cña vËt ®îc chän.
Híng dÉn : * tæ chøc d÷ liÖu : M¶ng hai chiÒu L(N,W) : L[i,j] lµ gi¸ trÞ tèi u cña valy khi träng lîng max lµ j
vµ xÐt c¸c vËt tõ 1-->i
* khëi trÞ : L[0,j]=0 víi mäi 0<=j <=W L[i,0]=0 víi mäi 0<=i<=N
* X©y dùng L theo c«ng thøc :
L[i,j] = Max (L[i-1,j-a[i]]+ C[i],L[i-1,j]) nÕu A[i]<=j
hoÆc L[i,j] = L[i-1,j] nÕu A[i]>J
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;
7
Const
infile = 'valy.inp';
outfile = 'valy.out';
MaxN
= 100;
MaxW
= 500;
Type
M1
M2
M3
Var
L
: M2;
A,C
: M1;
N,W
: integer;
f,g
: Text;
= array [0..maxW] of Word;
= array [0..maxN] of ^M1;
= array [1..maxn] of integer;
Procedure NhapDl;
var i:integer;
begin
Assign(f,infile);
Reset(f);
Readln(f,N,W);
for i:=1 to n do
Readln(f,A[i],C[i]);
Close(f);
end;
procedure ChuanBi;
var i,j:integer;
begin
for i:=0 to n do
begin
new(L[i]);
for j:=0 to w do
L[i]^[j]:=0;
end;
end;
function max(x,y:word):word;
begin
max:=x;
if xL[i-1]^[v] then
begin
Writeln(g,i,' ',a[i],' ',c[i]);
v:=v-a[i];
end;
Close(g);
end;
Begin
Clrscr;
8
NhapDl;
Chuanbi;
XuLi;
GhiKq;
End.
Bµi 4 : Bµi to¸n chia kÑo
Cho n gãi kÑo gãi thø i cã A[i] c¸i kÑo.Yªu cÇu h·y t×m c¸ch chia c¸c gãi kÑo nµy thµnh hai phÇn
sao cho ®é chªnh lÖch gi÷a tæng sè kÑo ë hai phÇn lµ nhá nhÊt cã thÓ.
D÷ liÖu vµo : file chiakeo.inp dßng ®Çu lµ sè n
dßng thø i trong sè n dßng tiÕp theo mçi dßng ghi sè A[i] lµ sè kÑo cã trong gãi thø i
(n<=100 vµ A[i]<=200)
kÕt qu¶ : file chiakeo.out dßng ®Çu tiªn lµ ®é chªnh lÖch min
c¸c dong sau ghi ra sè hiÖu c¸c gãi kÑo cña mét phÇn trong c¸ch chia t×m ®îc.
Híng dÉn : ®Ó t×m c¸ch chia c¸c gãi kÑo thµnh hai phÇn chªnh lÖch min th× cÇn chia sao cho tæng
sè kÑo trong mét phÇn gÇn víi gi¸ trÞ (Tong div 2) nhÊt, trong ®ã tong lµ tæng sè kÑo cña tÊt c¶ n
gãi. Ph¬ng ¸n quy ho¹ch cña ta ë ®©y lµ t×m ra mét sè c¸c gãi kÑo sao cho tæng sè kÑo cña nã gÇn
(tong div 2) nhÊt . §Ó lµm ®îc vËy ta dïng mét m¶ng D lµ m¶ng mét chiÒu vµ ta quy ho¹ch trªn
m¶ng Êy víi quy íc D[i]=0 th× kh«ng cã ph¬ng ¸n chän ra trong sè n gãi kÑo mét sè gãi ®Ó tæng sè
kÑo trong c¸c gãi ®îc chän lµ i
cßn D[i]<>0 th× cã ph¬ng ¸n chän ra mét sè gãi kÑo sao cho tæng sè kÑo c¸c gãi ®îc chän lµ i vµ
gãi cuèi cïng ®îc chän lµ D[i] nh vËy ta cÇn t×m mét gi¸ trÞ D[i]<>0 sao cho i lín nhÊt vµ kh«ng vît qu¸ (tong div 2) .
§Ó lµm ®îc vËy ban ®Çu ta chuÈn bÞ mét m¶ng D array[0..Tong div 2]
ë ®©y n<=100 a[i]<=200 nªn Tong<=20000 vËy kÝch thíc tèi ®a cña m¶ng D lµ 10000 ban ®Çu ta
cho D[0] nhËn mét gi¸ trÞ kh¸c 0 v× ban ®Çu ta khëi t¹o cha chän gãi kÑo nµo, c¸c gi¸ trÞ cßn l¹i cña
m¶ng D ta g¸n gi¸ trÞ 0.
ta lÇn lît xÐt tõng gãi kÑo tõ 1 --> n gi¶ sö khi xÐt ®Õn gãi thø i ta sÏ t×m xem nÕu cã thªm gãi kÑo
thø i th× nã cã thÓ thµnh lËp ®îc thªm nh÷ng tæng nµo cha ®îc thµnh lËp khi xÐt ®Õn gãi kÑo thø i-1
vµ cø nh vËy khi xÐt ®Õn gãi thø n th× ta cã ®îc tÊt c¶ c¸c c¸ch chia kh¸c nhau. Ta lµm nh sau
Fillchar(D,sizeof(D),0);
D[0]:=1;
For i:=1 to n do
For j:=Tong Div 2 downto A[i] do
If (D[j]=0) and (D[j-A[i]]<>0 ) then
D[j-A[i]]:=i;
ta g¸n D[j-A[i]]:=i lµ ®Ó thuËn tiÖn cho viÖc truy xuÊt kÕt qu¶.
Ch¬ng tr×nh nh sau :
Uses crt;
Const
infile
= 'Chiakeo.inp';
outfile = 'Chiakeo.out';
maxn
= 100;
maxT
= 10000;
Type
m1
= array [1..maxn] of byte;
9
m2
Var
= array [0..maxT] of byte;
a
: m1;
d
: m2;
n,clmin,dich,Tong : integer;
f,g
: Text;
procedure docdl;
var i,j:integer;
begin
assign(f,infile);
reset(f);
readln(f,n);
for i:=1 to n do
readln(f,a[i]);
close(f);
end;
procedure chuanbi;
var i,j:integer;
begin
fillchar(d,sizeof(d),0);
d[0]:=1;
tong:=0;
for i:=1 to n do
tong:=tong+a[i];
dich:=tong div 2;
end;
procedure qhoach;
var i,j:integer;
begin
for i:=n downto 1 do
for j:=dich downto a[i] do
if (d[j]=0) and (d[j-a[i]]<>0) then
d[j]:=i;
end;
procedure ghikq;
var i,j:integer;
begin
while (dich>0) and (d[dich]=0) do Dec(dich);
Clmin:=abs(Tong-2*dich);
assign(g,outfile);
rewrite(g);
writeln(g,Clmin);
While dich>0 do
begin
Writeln(g,d[dich]);
dich:=dich-a[d[dich]];
end;
close(g);
end;
Begin
Clrscr;
docdl;
chuanbi;
qhoach;
10
ghikq;
End.
Bµi 5 : di chuyÓn tõ t©y sang ®«ng
Cho ma trËn M*N mçi « chøa mét sè nguyªn ta cÇn di chuyÓn tõ mét « bÊt k× thuéc cét bªn tr¸i
sang mét « bÊt k× thuéc cét bªn ph¶i. Mçi bíc di chuyÓn tõ mét « (i,j) ta cã thÓ ®i sang « (i-1,j+1)
hoÆc (i,j+1) hoÆc (i+1,j+1). Chi phÝ cho mét ®êng ®i lµ tæng cña c¸c sè nguyªn trªn con ®êng ®ã.
Yªu cÇu h·y t×m ra mét con ®êng ®i víi chi phÝ thÊp nhÊt.
D÷ liÖu vµo : file Taydong.inp dßng ®Çu lµ sè m , n
dßng thø i trong sè m dßng tiÕp theo chøa n sè nguyªn trong ph¹m vi (-1000...1000) (m,n<=100)
KÕt qu¶ ra : file Taydong.out dßng ®Çu ghi mét nguyªn lµ chi phÝ min t×m ®îc.
n dßng tiÕp theo ghi chØ sè cña hµng lÇn lît di chuyÓn tõ t©y sang ®«ng.
VÝ dô:
taydong.inp
taydong.out
44
2431
8529
1746
9
1
1
2
1 7 8 9
1
Híng dÉn : theo c¸ch di chuyÓn nh vËy ta nhËn thÊy tíi « (i,j) cã thÓ ®i tõ « (i-1,j-1) (i,j-1) (i+1,j-1)
vµ nh vËy ta quy ho¹ch nh sau.
Dïng C lµ b¶ng 2 chiÒu M*N vµ C[i,j] lµ chi phÝ min ®Ó di chuyÓn tõ cét tr¸i tíi « (i,j) nh vËy chi
phÝ min ®Ó di chuyÓn tõ t©y-->®«ng lµ gi¸ trÞ nhá nhÊt cña cét thø n trong m¶ng C
C[i,j]:=Min(C[i-1,j-1],C[i,j-1],C[i+1,j-1]) + A[i,j];
CPMin=Min(C[i,n])
( 1<=i<=m)
Ch¬ng tr×nh díi ®©y dùa theo t tëng nh vËy nhng lµm ngîc l¹i tøc lµ quy ho¹ch tõ ®«ng sang t©y ®Ó
tiÖn cho viÖc ghi kÕt qu¶ vµ ta kh«ng khai b¸o thªm m¶ng C. M¶ng C nãi ë trªn chØ ®Ó lêi híng dÉn
®îc s¸ng sña cßn trong ch¬ng tr×nh ta cã thÓ quy ho¹ch ngay trªn m¶ng d÷ liÖu :
uses crt;
const infile
outfile
maxmn
maxc
Type
var
m1
= 'taydong.inp';
= 'taydong.out';
= 100;
= 1001;
= array [0..maxmn+1,1..maxmn] of integer;
a
: m1;
m,n,CPMin
: integer;
f,g
: text;
procedure DocDl;
var i,j:integer;
begin
Assign(f,infile);
Reset(f);
Readln(f,m,n);
for i:=1 to m do
begin
for j:=1 to n do
read(f,a[i,j]);
readln(f);
end;
Close(f);
11
end;
procedure ChuanBi;
var i,j:integer;
begin
for j:=1 to n do
begin
a[0,j]:=maxc;
a[m+1,j]:=maxc;
end;
end;
function Min(x,y,z:Integer):integer;
begin
if x>y then x:=y;
if x>z then x:=z;
Min:=x;
end;
procedure XuLi;
var i,j:integer;
begin
for j:=n-1 downto 1 do
for i:=1 to m do
A[i,j]:=Min(a[i-1,j+1],a[i,j+1],a[i+1,j+1])+A[i,j];
end;
procedure GhiKq;
var i,j,u,v,T:integer;
begin
Assign(g,outfile);
Rewrite(g);
CPMin:=A[1,1];i:=1;
for u:=2 to m do
if CPMin>A[u,1] then
begin
CPMin:=A[u,1];
i:=u;
end;
Writeln(g,CPMin);
for j:=1 to n-1 do
begin
Writeln(g,i);
T:= Min(a[i-1,j+1],a[i,j+1],a[i+1,j+1]);
if T = a[i-1,j+1] then Dec(i)
else if T = a[i+1,j+1] then Inc(i)
end;
Writeln(g,i);
Close(g);
end;
Begin
Clrscr;
DocDl;
ChuanBi;
XuLi;
GhiKq;
End.
Bµi 6 : Rót bµi ( c¸ch diÔn ®¹t kh¸c cña bµi nh©n ma trËn)
Cho n l¸ bµi xÕp trªn bµn vµ ®¸nh sè tõ 1 tíi n mçi l¸ mang mét sè nguyªn d¬ng theo ®óng thø tù ®·
xÕp lµ a1,a2,...,an . Mçi lÇn ta ®îc phÐp rót mét l¸ bµi ra khái d·y bµi ®ang xÕp vµ chi phÝ ®Ó rót l¸ bµi
thø i trong d·y lµ tÝch cña ba sè nguyªn lµ ba sè nghi trªn l¸ bµi rót ra vµ hai l¸ bµi ®Æt c¹nh nã ë thêi
®iÓm hiÖn t¹i.
12
(lu ý : víi c¸ch tÝnh chi phÝ nh vËy th× ta kh«ng rót hai l¸ bµi ë hai ®Çu. Mçi lÇn rót th× tËp bµi sÏ thu
hÑp l¹i mét l¸ vµ nh vËy cã sù thay ®æi vÒ vÞ trÝ bªn c¹nh cña hai l¸ bµi c¹nh l¸ võa rót)
Yªu cÇu : h·y rót ®i n-2 l¸ bµi víi chi phÝ nhá nhÊt. B¹n h·y t×m vµ in ra c¸ch rót ®ã
D÷ liÖu vµo : file card.inp dßng ®Çu tiªn lµ sè n dßng thø i trong n dßng tiÕp theo mçi dßng ghi sè
nguyªn ai (n<=100 ai<=100)
KÕt qu¶ ra : file card.out dßng ®Çu tiªn ghi chi phÝ min ®Ó rót n-2 l¸ bµi dßng thø i trong sè n-2 dßng
tiÕp theo bµi ghi chØ sè cña l¸ bµi ®îc rót theo sè hiÖu ban ®Çu.
Híng dÉn : dïng m¶ng hai chiÒu C[i,j] cã ý nghÜa lµ chi phÝ tèi thiÓu ®Ó rót hÕt c¸c l¸ bµi thuéc ®o¹n
[i,j] theo thø tù ban ®Çu, nh vËy C[i,j] ®îc tÝnh tõ c¸c gi¸ trÞ C[i,k-1] vµ C[k+1,j]
( i=
- Xem thêm -
.DOC 
46 
505 
133 
