Một số bài toán quy hoạch động

Đỗ Quang Tiến

Khi gặp một bài toán tin có yêu cầu tìm kết quả tốiưu về một hay nhiều tính chất nào đấy, hẳn không ít người nghĩ ngay đến sử dụnggiải thuật quy hoạch động để giải bài toán. Tại sao lại vậy Bởi vì quy hoạchđộng thường có độ phức tạp tính toán không cao nghĩa là chương trình sẽ chạycho ra kết quả đúng trong thời gian ngắn cho phép. Tuy nhiên, không phải bàitoán với yêu cầu tối ưu nào cũng có thể giải bằng quy hoạch động, mặt khác cũngcó không ít bài toán đúng là có thể giải bằng quy hoạch động nhưng việc pháthiện và áp dụng phương pháp này để giải là không đơn giản.

Việc phát hiện cũng như áp dụng quy hoạch động đểgiải bài toán phụ thuộc rất lớn vào khả năng tư duy của bạn và đặc biệt lànhững kinh nghiệm mà bạn có.

Bài viết này sẽ không đề cập đến những khái niệm cơbản của quy hoạch động vì những khái niệm này đã quá quen thuộc với mọi người.Bài viết chỉ dừng ở mức phân tích cụ thể lời giải của một số bài toán khá hay,từ đó hy vọng ít nhiều giúp bạn có thêm một chút kinh nghiệm trong lập trìnhgiải quyết các bài toán tin.

Trước tiên ta cùng xét một bài toán đã được sử dụngtrong kỳ thi Olympic Tin học sinh viên Thủ đô năm 1998.

Bài 1. Giá trị biểu thức

Giả thiết X,Ylà hai số nguyên dương. Kí hiệu Sx là tổng các chữ số trong dạngbiểu diễn cơ số 10 của X, Dmax_y là chữ số lớn nhất và Dmin_y là chữ số nhỏnhất trong dạng biểu diễn cơ số 10 của Y. Phép tính hai ngôi # với các toánhạng nguyên dương X,Y được định nghĩa như sau:

( X#Y ) = Sx*Dmax_y+ Dmin_y

Ví dụ:

(30#9) = 3*9 +9 = 36

(9#30) = 9*3 +0 = 27

Với X chotrước, một số biểu thức hợp lệ là:

(X#X)

((X#X)#X)

(X#(X#X)#(X#X)#X)

Ký hiệu kết quảbiểu thức là K. Cho X và K (0 < X,K < 109-1) cần xác định sốít nhất m các phép # để từ đó có thể xây dựng biểu thức thuộc dạng đang xét vớiX cho kết quả K và biểu diễn của biểu thức.

Dữ liệu vào từfile văn bản BT.IN, dòng thứ nhất chứa X, dòng thứ hai chứa K.

Kết quả ra filevăn bản BT.OUT, dòng thứ nhất chứa m, dòng thứ hai chứa biểu thức.

Ví dụ:

BT.IN

BT.OUT

718

81

3

((718 #(718 #718)) #718)

* * *

Thực ra đề bàinày cũng dễ hiểu không phức tạp lắm, bây giờ ta đi vào phân tích tìm lời giảicho bài toán. Trước tiên nhận xét rằng cho 0 < X, K < 109 nên:

1 ≤ Sx ≤ 9*9

1 ≤ Dmax_x ≤ 9

0 ≤ Dmin_x ≤ 9

Từ đó 1 ≤ X#X ≤ 9*9*9+9 = 738, tức là biểu thức có một dấu # luôn mang giá trị trong đoạn [1,738]. Suy rộnghơn thì giá trị của một biểu thức hợp lệ bất kỳ phải nằm trong đoạn [1,738],đây chính là cốt lõi lời giải cho bài toán.

Rõ ràng ta chỉchấp nhận các giá trị K thoả mãn 1 ≤ K ≤ 738, nếu K nằm ngoài khoảng này thì chắc chắn vô nghiệm.

Xét biểu thứcX#X có 1 dấu #, dễ thấy có 3 cách mở rộng biểu thức 1 dấu # này là:

- X#(X#X)

- (X#X)#X

- (X#X)#(X#X)

Giả sử B là mộtbiểu thức tạo bởi X và n dấu # thế thì có 3 cách mở rộng biểu thức này là:

- X#B (n+1dấu #)

- B#X (n+1dấu #)

- B#B (2*n+1dấu #)

Ta lập mảng mộtchiều L[1..738] trong đó L[i] cho biết số phép # ít nhất để từ X tạo ra kết quảlà i, i=1..738. Dễ thấy mảng L mang tính truy hồi, lần ngược và khi làm cụ thểta thực hiện như sau:

1. Khởi tạomảng A[1..738] := 0, mảng A đánh dấu các giá trị đã tạo được từ biểu thức có Xvà #; khởi tạo mảng L nhận các giá trị Maxint.

2. Tìm T=X#X;A[T]:=1; L[T]:=1

3. Thực hiệnbước 3 cho đến khi mảng L không còn bị thay đổi:

For i:=1 to 738

Nếu A[i]=1 thì

t:=X#i;

Nếu L[t]>L[i]+1thì

L[t]:=L[i]+1;A[t]:=1;

t:=i#X;

Nếu L[t]>L[i]+1thì

L[t]:=L[i]+1;A[t]:=1;

t:=i#i;

Nếu L[t]>2*L[i]+1thì

L[t] :=2*L[i]+1;A[t]:=1;

L[K] cho số phép # tối thiểu của biểu thức cần tìm.

Để hoàn thiện chương trình tất nhiên phải thiết kếthêm mảng lưu trữ thế nào để sau này khi in kết quả có thể đưa ra được cả vịtrí các dấu # và các dấu ngoặc của biểu thức. Trong chương trình dưới đây, mảngPre và D có chức năng này. Sau đây là toàn văn chương trình giải bài "Giátrị biểu thức":

{GiaTri Bieu Thuc - Qui hoach dong DQT }

uses crt;

const

nmax=738;

inp='bt.in';

out='bt.out';

var

f:text;

x,k :longint;

stop :boolean;

a,d :array[1..nmax]of byte;

l,pre:array[1..nmax]of integer;

procedure Nhap;

assign(f,inp);

reset(f);

readln(f,x); readln(f,k);

close(f);

end;

function TinhGiaTri(x,y:longint):integer;

var i,k,dmax,dmin,sx:byte;

st:string;

c:integer;

str(y,st);

dmax:=0; dmin:=9;

for i:=1 to length(st) do

val(st[i],k,c);

if kthen dmin:=k;

if k>dmax then dmax:=k;

end;

str(x,st);

sx:=0;

for i:=1 to length(st) do

val(st[i],k,c);

sx:=sx+k;

end;

TinhGiaTri:=sx*dmax+dmin;

end;

procedure TimBieuThuc;

var i,t,top:integer;

fillchar(a,sizeof(a),0);

for i:=1 to 738 do L[i]:=maxint;

{---}

t:=TinhGiaTri(x,x);

a[t]:=1; l[t]:=1;

stop:=false;

while not stop do

stop:=true;

for i:=1 to nmax do

if a[i]=1 then

t:=TinhGiaTri(x,i);

if l[t]>l[i]+1 then

a[t]:=1; l[t]:=l[i]+1;

pre[t]:=i; d[t]:=1; stop:=false;

end;

{---}

t:=TinhGiaTri(i,x);

if l[t]>l[i]+1 then

a[t]:=1; l[t]:=l[i]+1;

pre[t]:=i; d[t]:=2; stop:=false;

end;

{---}

t:=TinhGiaTri(i,i);

if l[t]>2*l[i]+1 then

a[t]:=1; l[t]:=2*l[i]+1;

pre[t]:=i; d[t]:=3; stop:=false;

end;

end;

end;

procedure path(t:integer);

if pre[t]<>0 then

write(f,'(');

case d[t] of

1: begin

write(f,x,'#'); path(pre[t]);

end;

2: begin

path(pre[t]); write(f,'#',x);

end;

3: begin

path(pre[t]); write(f,'#'); path(pre[t]);

end;

end;

write(f,')');

end

else write(f,'(',x,'#',x,')');

end;

procedure Xuly_Inkq;

assign(f,out);

rewrite(f);

if k>738 then writeln(f,'0')

else

TimBieuThuc;

if a[k]=0 then writeln(f,'0')

else

writeln(f,l[k]); path(k);

end;

end;

close(f);

end;

BEGIN

clrscr;

Nhap;

Xuly_Inkq;

END.

Nhận thấy rằng cái khoá của bài trên là giớihạn của kết quả biểu thức từ đó nếu chịu khó suy nghĩ thì từ cái khoá nàycó thể mở ra, phát triển thành rất nhiều bài toán tương tự. Tiếp theo ta phântích một bài toán khác có cách giải, dĩ nhiên, vẫn là qui hoạch động nhưng ởmột hình thức biểu hiện khác.

Bài 2 : Lịch thuê nhân công

Có một dự án kéo dài trong T tháng và người quản lýcần phải lập lịch sử dụng công nhân trong dự án, anh ta biết số công nhân tốithiểu cần trong mỗi tháng. Mỗi khi thuê hay sa thải một công nhân thì đều phảimất một chi phí xác định, mỗi công nhân được thuê sẽ vẫn nhận được lương thángngay cả khi không sử dụng anh ta làm việc.

Với mỗi côngnhân, người quản lý biết chi phí thuê, chi phí sa thải và tiền lương phải trảcho công nhân đó trong 1 tháng. Và bài toán đặt ra như sau: Cần phải thuê haysa thải bao nhiêu công nhân mỗi tháng để tổng chi phí dành cho nhân công của dựán là nhỏ nhất, tức là giảm tối đa chi phí của dự án.

Dữ liệu vào từfile văn bản EMPLOY.IN có cấu trúc như sau:

- Dòng đầughi T là số tháng diễn ra dự án (T=<100).

- Dòng thứhai ghi 3 số lần lượt là chi phí thuê, lương tháng, chi phí sa thải mỗi côngnhân.

- Dòng cuốicùng là T số nguyên dương, số thứ i cho biết số công nhân tối thiểu cần chotháng thứ i, các giá trị số không quá 150.

Kết quả ra filevăn bản EMPLOY.OUT theo định dạng:

- Dòng thứnhất ghi tổng chi phí nhỏ nhất tìm được.

- Dòng thứhai ghi T số, số thứ i là số công nhân hoạt động trong dự án tại tháng thứ i.

Ví dụ về filedữ liệu vào và file kết quả ra:

EMPLOY.IN

EMPLOY.OUT

3

4 5 6

10 9 11

265

10 10 11

* * *

Đề bài này hơirắc rối khó hiểu một chút vì vậy cần phải đọc kỹ, nắm chắc. Rõ ràng việc thuêthêm hay sa thải công nhân đều phải chịu phí tổn nên thấy: để đảm bảo chi phíít nhất cho việc thuê nhân công trong cả dự án thì số công nhân đang thuê trongmột tháng không nhất thiết phải là số công nhân tối thiểu cần cho tháng đấy. Vídụ, phí tổn để thuê cũng như sa thải công nhân rất lớn thì không dại gì ta lạithường xuyên thuê rồi lại sa thải người trong từng tháng, tốt nhất nên giữ họvà trả lương (dù họ không làm gì). Nhiệm vụ của chúng ta trong mỗi tháng phảiquyết định có bao nhiêu công nhân trong biên chế thuê, nghĩa là phải quyết địnhxem cần thuê hay cần sa thải bao nhiêu công nhân trong biên chế của thángtrước. Nếu gọi T_max là số công nhân của tháng cần nhiều người nhất thì rõ ràngsố công nhân trong biên chế thuê của một tháng bất kỳ trong dự án không bao giờvượt quá T_max. Xét một tháng nào đó, biết rằng không nên sử dụng quá T_maxngười và cũng không được phép sử dụng ít hơn số người tối thiểu cần cho thángđấy, nhưng phải chọn giá trị nào trong khoảng giới hạn này Đến đây nếu các giátrị của T và T_max là nhỏ thì có thể duyệt tìm ra kết quả tối ưu nhưng do cácgiá trị này lại có thể khá lớn nên buộc phải tìm cách khác hiệu quả hơn.

Lập mảngScn[1..T], Scn[i] cho biết số công nhân tối thiểu cần cho tháng thứ i, i=1..T(mảng này nhập vào từ file input). Lập thêm mảng C[T,T_max] trong đó C[i,j] chobiết chi phí tối thiểu của i tháng đầu tiên của dự án nếu tại tháng thứ i có jcông nhân trong biên chế thuê (i=1..T, j=1..T_max). Thấy là giá trị C[i,j] cóthể xác định thông qua các giá trị C tại tháng i-1 (là tháng trước):

C[i,j] = Min{C[i-1,k] + chi phí để từ k người thành j người }

( i=1..T;j=Scn[i]..T_max; k=Scn[i-1]..T_max)

Bài toán đã đơngiản hơn nhiều khi có được công thức truy hồi và vì độ phức tạp tính toán khônglớn nên chắc chắn chương trình sẽ ngắn gọn, cho kết quả tối ưu trong thời gianrất ngắn. Kết quả tối ưu cuối cùng là:

Kq = Min{C[T,j]+ chi phí sa thải j người}

(j=Scn[T]..T_max)

Để có thể đưa ra kết quả đầy đủ(số công nhân sử dụng mỗi tháng) thì cần thêm mảng hai chiều Pre, trong đóPre[i,j] := k, với i=1..T; j=Scn[i]..T_max; k thoả mãn tổng (C[i-1,k] + chi phíđể từ k người thành j người) nhỏ nhất. Việc lần ngược tìm kết quả trong mảngPre không khó.

Nếu bạn từng làm nhiều bài Tin dùng qui hoạch độngđể giải thì chắc bạn thấy rằng qui hoạch động chỉ là một phương pháp rất chung,khi áp dụng vào mỗi bài một khác, không bài nào giống bài nào. Để minh họa điềunày, mời các bạn đón đọc tiếp trong số sau ta cùng xét thêm một số bài toán tinkhá hấp dẫn nữa.

Một số bài toán quy hoạch động

Đỗ Quang Tiến

(Tiếp theo sốtrước)

Bài 4. Xoay ô

(Đề bài đã được đăng trên sốbáo trước)

Thực ra đâykhông phải là một bài dễ dàng ngay cả với những người nhiều kinh nghiệm giảitoán tin. Không ít người gặp bài này phải bó tay hay buộc phải dùng duyệt đểgiải quyết cho dù duyệt tốt đến mấy cũng không thể chạy được với những test cókích thước tối đa. Thế nhưng bài này lại có thể dùng qui hoạch động giải quyếtvới độ phức tạp tính toán không cao lắm cỡ O(2N*M). Và ta sẽ phân tíchcụ thể cách giải bài này bằng qui hoạch động.

Đầu tiên phảichú ý đến một đặc điểm bất thường của đề bài: giới hạn số ô tối đa trên mộtdòng là 8 trong khi số dòng tối đa lại là 50, chắc không phải ngẫu nhiên lại cógiới hạn này. Như đề bài cho biết, mỗi ô được chia làm 4 miền: trên, trái,dưới, phải; mỗi miền lại được tô một trong hai màu đen hoặc trắng, tô màu đenứng với một số 1, tô màu trắng ứng với số 0. Giả sử ta xét tại một dòng nào đó,miền trên của các ô trên dòng này theo thứ tự từ trái sang phải tạo lên một xâunhị phân; miền dưới của các ô trên dòng này cũng vậy, cũng tạo nên một chuỗinhị phân. Nếu phải thoả mãn điều kiện các miền chung cạnh ô phải cùng màu thìdễ thấy chuỗi nhị phân của miền dưới của một dòng chính là chuỗi nhị phân của miềntrên của dòng tiếp theo trong bảng. Từ nhận xét này ta đang dần hình dung racách giải. Nhắc lại rằng số ô tối đa trên một dòng là 8 tức là chuỗi nhị phâncủa miền trên hoặc dưới của một dòng có độ dài không quá 8. Hiển nhiên mỗichuỗi nhị phân này có thể ứng với một số trong hệ thập phân và số này nằm trongkhoảng (0,2N), N =< 8.

Bây giờ ta xétmột bài toán con: ta sẽ đánh giá cụ thể 1 dòng của bảng này và biết rằng cácmiền trên của dòng có thể ứng với một số, miền dưới cũng ứng được với một số;nếu giả sử cho hai số Mt, Md, phải tìm cách xoay một số ít nhất các ô trên dòngsao cho dòng thoả mãn: các miền trên của dòng phải tương ứng tạo nên Mt, cácmiền dưới tương ứng tạo thành Md, các miền còn lại nếu chung cạnh ô thì phảicùng màu, ngoài ra còn cần xác định những ô nào được xoay nữa. Thực ra với bàitoán con có số lượng ô trên một dòng không quá 8 thì có thể dùng duyệt chạycũng khá hiệu quả. Nhưng nếu ta mở rộng bài toán này thành một bài khác, giả sửsố ô xét không quá 200 chẳng hạn, thì chắc chắn phải tìm cách khác thôi. Vàcách được đề xuất cho bài mở rộng này lại là qui hoạch động. Tuy nhiên nó cũngkhông quá phức tạp lắm, bạn hãy thử tự giải quyết xem.

Quay trở lạibài xoay ô của chúng ta, vấn đề trạng thái của một dòng đã được giải quyết, giờlà kết hợp trạng thái các dòng để đưa ra lời giải chung. Bắt đầu bằng việcthiết lập mảng hai chiều D[1..M, 1..2N], D[i,j] cho biết số ô tốithiểu đã xoay để i dòng đầu tiên của mảng thoả mãn yêu cầu đề bài và miền dướicủa dòng thứ i tạo lên số j (i=1..M, j=1..2N), thế thì dễ thấy:

D[i,j] = Min { D[i-1,k] + Xikj}

i=1..M; j=1..2N;k=1..2N

Xikj là số tốithiểu các ô trên dòng i được xoay để dòng i có miền trên tương ứng k, miền dướitương ứng là j.

Gọi KqMin là kết quả tốiưu nhất tức là số tối thiểu các ô phải xoay đối với cả bảng M dòng thì:

KqMin = Min { D[M,k] ,k=1..2N }

Như vậy dùng mảng D làbiết số ô tối thiểu cần xoay sao cho thoả mãn điều kiện đặt ra của đề bài nhưngchúng ta còn một yêu cầu nữa chưa thực hiện được là cần cho biết những ô nàođược xoay. Yêu cầu này thì mảng D chịu, không thể cho biết được, vì vậy tathiết kế thêm một mảng nữa, mảng hai chiều Pre[1..M,1..2N]. Do biết:

D[i,j] = Min { D[i-1,k] + Xikj }

nên ta gán Pre[i,j]=k trongđó k là giá trị mà D[i-1,k] + Xikj nhỏ nhất. Khi viết ra kết quả vàofile output ta chỉ cần lần ngược trong mảng Pre, bạn hãy tự giải quyết lấy, nókhông quá phức tạp đâu.

Nếu muốn, bạn hãy thamkhảo toàn bộ chương trình giải bài Xoay ô ở sau, về cơ bản thì chương trìnhđã thể hiện được giải thuật nhưng cụ thể từng bước cài đặt chưa chắc đã tối ưu,bạn có thể thay đổi, chỉnh sửa cho hợp lý.

{ Xoay Cac O - Qui hoach dong - DQT }

uses crt;

const

inp='xoay.in';

out='xoay.out';

mmax=50;

nmax=8;

tt :array[1..8]of byte=(1,3,7,15,31,63,127,255);

x :array[1..4]of byte=(0,1,1,1);

type

m_int=array[0..mmax,0..255]of word;

m_byt=array[0..mmax,0..255]of byte;

tto=array[1..4]of byte; {trangthai o}

var

f:text;

m,n,ttmax:byte; {trang thaiMax}

a:array[1..mmax,1..nmax]of tto; {trang thaidau nhap tu input}

pre:m_byt; {so ung voi cac mientren tren 1 dong}

d:m_int;

{d[i,j] - so o xoay it nhat de dua dongi ve trang thai j}

{Danh cho tim cach xoay}

bt,bd :byte;{bit tren, bit duoi}

xmo :array[1..4]of tto; {xet 4trang thai tai mot o}

trai,sbd,prex:array[1..nmax,1..4]of word;{sbd - so bien doi}

procedure Nhap;

var i,j,k:byte;

assign(f,inp);

reset(f);

readln(f,m,n);

for i:=1 to m do

for j:=1 to n do

for k:=1 to 4 do read(f,a[i,j,k]);

readln(f);

end;

close(f);

end;

procedure KhoiTao;

var i:byte;

ttmax:=tt[n];

for i:=0 to ttmax do

d[0,i]:=0;

pre[0,i]:=0;

end;

end;

procedure GetBit(so,vt:byte;var bit:byte);

bit:=(so shr vt) and 1;

end;

procedure xoay90(tto1:tto;var tto2:tto);

tto2[1]:=tto1[2]; tto2[2]:=tto1[3];

tto2[3]:=tto1[4]; tto2[4]:=tto1[1];

end;

procedure xoay180(tto1:tto;var tto2:tto);

tto2[1]:=tto1[3]; tto2[2]:=tto1[4];

tto2[3]:=tto1[1]; tto2[4]:=tto1[2];

end;

procedure xoay270(tto1:tto;var tto2:tto);

tto2[1]:=tto1[4]; tto2[2]:=tto1[1];

tto2[3]:=tto1[2]; tto2[4]:=tto1[3];

end;

procedure tinh_xoay(i,st,sd:byte;vartemp:integer;var ttc:byte);

var

k,t,s:byte;

xmo[1]:=a[i,1]; xoay90(a[i,1],xmo[2]);

xoay180(a[i,1],xmo[3]);xoay270(a[i,1],xmo[4]);

getbit(st,0,bt); getbit(sd,0,bd);

for t:=1 to 4 do

if (xmo[t,1]=bt)and(xmo[t,3]=bd) then

trai[1,t]:=xmo[t,4]; sbd[1,t]:=x[t];

end

else trai[1,t]:=2;

{}

for k:=2 to n do

xmo[1]:=a[i,k];xoay90(xmo[1],xmo[2]);

xoay90(xmo[2],xmo[3]);xoay90(xmo[3],xmo[4]);

getbit(st,k-1,bt); getbit(sd,k-1,bd);

for t:=1 to 4 do

sbd[k,t]:=maxint;

for s:=1 to 4 do

if(xmo[t,1]=bt)and(xmo[t,2]=trai[k-1,s])and(xmo[t,3]=bd)

and(sbd[k,t]>sbd[k-1,s]+x[t]) then

sbd[k,t]:=sbd[k-1,s]+x[t];

trai[k,t]:=xmo[t,4];

prex[k,t]:=s;

end;

end;

end;

temp:=maxint;

for k:=1 to 4 do

if temp>sbd[n,k] then

temp:=sbd[n,k];

ttc:=k;

end;

end;

procedure Xuly;

var i,j,k,ttc:byte;

temp:integer;

for i:=1 to m do

for j:=0 to ttmax do

d[i,j]:=maxint;

for k:=0 to ttmax do

Tinh_xoay(i,k,j,temp,ttc);

if d[i,j]>d[i-1,k]+temp then

d[i,j]:=d[i-1,k]+temp;

pre[i,j]:=k;

end;

end;

end;

end;

end;

procedure Sua_Mang_Ăi,ttc:byte);

var k,t:byte;

for k:=n downto 1 do

case ttc of

2:xoay90(a[i,k],a[i,k]);

3:xoay180(a[i,k],a[i,k]);

4:xoay270(a[i,k],a[i,k]);

end;

ttc:=prex[k,ttc];

end;

end;

procedure Inkq;

var

min,temp:integer;

i,j,k,ttc,vt:byte;

min:=maxint;

for i:=0 to ttmax do

if d[m,i]<>

min:=d[m,i];

vt:=i;

end;

{---}

assign(f,out);

rewrite(f);

if min<>maxint then

writeln(f,min);

for i:=m downto 1 do

Tinh_Xoay(i,pre[i,vt],vt,temp,ttc);

Sua_mang_Ăi,ttc);

vt:=pre[i,vt];

end;

for i:=1 to m do

for j:=1 to n do

for k:=1 to 4 do write(f,a[i,j,k]:2);

writeln(f);

end;

end

else writeln(f,'No Solution.');

close(f);

end;

BEGIN

clrscr;

Nhap;

KhoiTao;

XuLy;

Inkq;

END.

Phải nói rằng "Xoay ô" là một bài qui hoạch độnghay, đặc biệt nó lại chứa đựng bên trong một bài toán con khác cũng dùng quihoạch động để giải. Tuy nhiên khi N=8 thì chương trình chạy cũng hơi lâu, và cóhạn chế là cách giải này không thể thực thi khi N ≥ 9.