Thuật toán chia kẹo

Thuật toán chia kẹo Nguyễn Ngọc Thắng Một bài toán được gọi là một bàitoán hay nếu nó là một bài toán khó và có lời giải độc đáo. Bài toán "Chia kẹo" là một minh chứng cho điềuđó. Bài toán này có phương pháp giải đặc biệt, tư tưởng của nó có thể được ápdụng để giải cho rất nhiều bài toán khác trong Tin học. Các bạn có thể thamkhảo bài viết "Thuật toán chia kẹo và ứng dụng giải lớp bài toán chianhóm" của tác giả Lã Thành Công trên số báo tháng 1/2001. Sauđây tôi xin trình bày phương pháp giải bài toán này và ứng dụng thuật toántrong việc giải các bài toán tin khác. Nhắc lại bài toán chia kẹo Có N gói kẹo, gói thứ i có Aicái kẹo. Không được bóc bất kỳ một gói kẹo nào, cần chia N gói kẹo thành haiphần sao cho độ chênh lệch số kẹo giữa hai gói là ít nhất. Dữ liệu vào trong file "chiakeo.inp" có dạng : - Dòng đầu tiên là số N(N<=100); - Dòng thứ hai là N số Ai(i=1, 2,.., N; Ai <=100). Kết quả ra file "chiakeo.out" có dạng: - Dòng đầu là độ chênh lệchnhỏ nhất giữa hai phần có thể được. - Dòng hai là một dãy N số,nếu si =1 thì gói thứ i thuộc phần 1, nếu si =2 thì góithứ i thuộc phần 2 Thuật toán: Với một số M bất kì, nếu ta biếtđược có tồn tại một cách chọn các gói kẹo để tổng số kẹo của các gói được chọnbằng đúng M không, thì bài toán được giải sẽ quyết. Vì đơn giản là ta chỉ cầnchọn số M sao cho M gần với Ai/2nhất (với i =1,2,..,N). Sau đó xếp các gói kẹo để tổng bằng M vào phần một,phần thứ hai sẽ gồm các gói kẹo còn lại. Để kiểm tra được điều trên ta sẽ xâydựng tất cả các tổng có thể có của N gói kẹo bằng cách: ban đầu chưa có tổngnào được sinh ra. Làm lần lượt với các gói kẹo từ 1 đến N, với gói kẹo thứ i,ta kiểm tra xem hiện tại có các tổng nào đã được sinh ra, giả sử các tổng đó làx1, x2,.., xt vậy thì đến bước này sẽ có thểsinh ra các tổng x1, x2,.., xt và Aivà x1+Ai,x2+Ai,..,xt+Ai.Với N gói kẹo, mà mỗi gói có không quá 100 cái kẹo vậy tổng số kẹo không vượtquá N*100 <= 10000 cái kẹo. Dùng mảng đánh dấu D, nếu có thể sinh được ratổng bằng k thì D[k] = 1 ngược lại D[k] = 0. Chương trình thể hiện thuật toántrên. {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+,Y+} {$M 16384,0,655360} Program chia_keo; uses crt; const max = 100; fi ='chiakeo.inp'; fo ='chiakeo.out'; var a,s : array[1..max]of integer; d1,d2,tr : array[0..max*max]of integer; n,m,sum : integer; Procedure docf; var f: text; k : integer; begin assign(f,fi); reset(f); readln(f,n); sum:=0; for k:=1 to n do begin read(f,a[k]); sum:=sum+a[k]; end; close(f); end; Procedure lam; var i,j : integer; Begin fillchar(d1,sizeof(d1),0); fillchar(tr,sizeof(tr),0); d1[0]:=1;d2:=d1; for i:=1 to n do begin for j:=0 to sum-a[i] do if (d1[j]=1)and(d2[j+a[i]]=0) then begin d2[j+a[i]]:=1; tr[j+a[i]]:=i; end; d1:=d2; end; end; Procedure ghif; var m,k : integer; f :text; Begin fillchar(s,sizeof(s),0); m:=sum div 2; while d2[m]=0 do dec(m); assign(f,fo); rewrite(f); writeln(f,sum-2*m); while tr[m]>0 do begin s[tr[m]]:=1; m:=m-a[tr[m]]; end; for k:=1 to n do write(f,k+1,#32); close(f); end; BEGIN {main} docf; lam; ghif; END. Nhận xét:Chương trình trên đây cài đặt rất "thô", song dễ hiểu. Chương trình có thể cảitiến lại để có thể chạy được số liệu lớn hơn, nhanh hơn. Ví dụ: bạn có cần để ýđến các tổng >sum/2 không? Có thể tích hợp cả ba mảng D1, D2 và TR làm mộtmảng không? Bạn đọc hãy chỉnh lại để chương trình chạy tốt hơn. Sau đây là các lớp bài toán ápdụng thuật toán chia kẹo. Bài nào đơn giản tôi chỉ đưa thuật toán để các bạntham khảo. Còn chương trình bạn đọc tự cài đặt. Bài toán mua bán hàng Có một người đi mua hàng, anhta có N đồng tiền d1, d2,.., dN. Người bánhàng có M đồng tiền b1, b2,.., bm. Anh tamuốn mua một mặt hàng với giá trị W. Hỏi cuộc mua bán có thể diễn ra đượckhông? Giới hạn: M, N<=100 và di,bj <=100. Thuật toán: Bài này áp dụng một cách trực tiếp bài toán chia kẹo.Xây dựng các tổng có thể có của người mua hàng, người bán hàng. Sau đó kiểm traxem có tồn tại hai số i, j thoả mãn: i là tổng có thể sinh ra của người mua, jlà tổng có thể sinh ra của người bán và i-j =M. Bài toán xoay DOMINO Cho N thanh DOMINO xếp theo chiềudọc như hình vẽ. Vídụ hình trên gồm 5 thanh DOMINO. Mỗi thanh DOMINO gồm 2 phần, phầntrên và phần dưới. Trên mỗi phần có một số từ 1 đến 6. Yêu cầu đặt ra là hãy tìmcách xoay các thanh (xoay 180 độ) để sau khi xoay chênh lệch giữa tổng trên vàtổng dưới là ít nhất. Giới hạn: N<=1000. Thuật toán Ta xây dựng mảng Wi làđộ chênh lệch giữa phần trên và phần dưới của thanh DOMINO thứ i. Nếu các số Wi>= 0 thì đây là một bài toán chia kẹo. Để các số Wi không âm tachỉ cần đảo lại các thanh mà Wi < 0. Sau đó dùng thuật toán chia kẹo để giải. Bài toán ngân hàng trả tiền Một người đi lấy tiền ở một ngânhàng. Anh ta cần lấy một khoản đúng M đồng. Ngân hàng có N đồng tiền A1,A2,.., AN. Hỏi ngân hàng có bao nhiêu cách trả tiền. Dữ liệu vào trong file:"MONEY.INP" có dạng: + Dòng đầu là hai số N và M (N <=100, M <= 10000) + Các dòng tiếp theo là các phần tử của mảng A. Kết quả ra file: "MONEY.OUT" gồmmột dòng duy nhất là số cách trả tiền (Số cách trả tiền < Maxlongint) Ví dụ: Thuật toán: Bài toán này khác với bài toán chia kẹo, nhưngđể giải ta vẫn áp dụng tư tưởng chia kẹo. Nó không đơn thuần là tìm được mộtcách trả tiền, mà là tìm số cách trả tiền. Với bài này ta cũng sinh ra tất cảcác tổng, song mảng D (mảng đánh dấu) không đơn thuần là bằng 1 hay bằng 0 mànó có ỹ nghĩa là số cách tạo ra tổng đó. Chương trình thể hiện thuật toán: {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+,Y+} {$M 16384,0,655360} Program tra_tien; uses crt; const max = 100; limit = 1000; fi = 'money.inp'; fo = 'meney.out'; var D : array[0..limit]of longint; a : array[1..max]ofinteger; n, m : longint; Procedure docf; var f : text; k :integer; Begin assign(f,fi); reset(f); readln(f,n,m); for k:=1 to n do read(f,a[k]); close(f); end; Procedure lam; var i,j :integer; Begin fillchar(D,sizeof(D),0); D[0]:=1; for i:=1 to n do for j:=m-a[i] downto 0 do inc(D[j+a[i]],D[j]); end; Procedure ghif; Var f :text; Begin assign(f,fo); rewrite(f); write(f,D[m]); close(f); End; BEGIN {main} docf; lam; ghif; END. Bài toán dãy có tổng chia hết chok (đề thi toàn Quốc) Cho một dãy số nguyên A1,A2,.., AN và một số k. Hãy tìm một dãy con (không nhấtthiết phải liên tiếp nhau) dài nhất có tổng các số chia hết cho số k. Dữ liệu vào trong file "dayso.inp" có dạng: + Dòng 1 gồm 2 số N và k(N<=1000; k<=50) + Các dòng tiếp theo chứa các sốcủa mảng A. Kết quả ra file "dayso.out" gồm một dòng ghi số phần tửlớn nhất tìm được. Ví dụ: Thuật toán: Tìmdãy nhiều phần tử nhất tương đương với việc loại khỏi dãy ít phần tử nhất đểcác phần tử còn lại có tổng chia hết cho k. Ta gọi d là số dư của tổng tất cảcác phần tử của dãy A chia cho k. Nếu ta chọn được ít phần tử nhất (thậm chí cóthể không chọn) để tổng các số được chọn chia k cũng dư d thì các phần tử còn lạilà dãy cần tìm. Với bài này ta cũng sinh ra cáctổng có thể có, song ta xếp các tổng có cùng số dư khi chia cho k làm một lớp.Ta chỉ cần quan tâm tới các lớp mà không cần quan tâm tới các tổng. Sẽ có klớp, lớp một là gồm các tổng chia cho k dư 1, lớp 2 là gồm các tổng chia cho kdư 2,..., lớp k-1 là gồm các tổng chia cho k dư (k-1), lớp k là gồm các tổngchia hết cho k. Bài toán này khác với bài toánchia kẹo là phải đòi hỏi tìm ít phần tử nhất. Để làm được điều này ta sẽ dùngthêm một mảng nhãn. Như vậy theo thuật toán trên tacó thể làm được với dữ liệu rất lớn so với đề bài. Chương trình sau có thể giải vớiN <=100000 và k <= 100. {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+,Y+} {$M 16384,0,655360} Program day_so; uses crt; const maxK = 100; fi ='dayso.inp'; fo ='dayso.out'; var L1,L2 :array[0..maxK]of longint; n,k,p : longint; Procedure lam; var f : text; i,j,x : longint; Begin fillchar(L1,sizeof(L1),0); L2:=L1; assign(f,fi); reset(f); readln(f,n,k); p:=0; for i:=1 to n do begin read(f,x); x:=x mod k+k; p:=(p+x)mod k; for j:=0 to k-1 do if (L1[j]>0) then if (L2[(x+j)mod k]=0)or(L2[(x+j)mod k]>L1[j]+1) then L2[(x+j)modk]:=L1[j]+1; L2[x mod k]:=1; end; close(f); end; Procedure ghif; var f :text; Begin assign(f,fo); rewrite(f); write(f,n-L2[p]); close(f); End; BEGIN {main} lam; ghif; END. Nếu bạn muốn tìm dãy con này thìđây là một công việc khác phức tạp. Trước tiên bạn phải tìm ra các phần tử cầnloại bỏ. Sau đó đọc lại file một lần nữa. Nhưng việc tìm ra các số cần loại bỏkhông đơn giản. Nguyên nhân gây ra việc khó khăn này là mảng trước bị ghi đè.Song không phải là không giải được. Tôi có một cách làm nhưng cách làm đó khádài dòng, chưa tốt. Bạn nào có cách làm tốt, hay có thắc mắc gì xin liên hệ vớitoà soạn.