Thuật toán chia kẹo

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ápgiả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áctrong Tin học.
Nội dung trích xuất từ tài liệu:
Thuật toán chia kẹo Thuật toán chia kẹo Nguyễn Ngọc ThắngMộ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ápgiả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áctrong 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ụnggiả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ántrongviệc giải các bài toán tin khác.Nhắc lại bài toán chia kẹoCó 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 chiaN 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(NChươ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;beginassign(f,fi); reset(f);readln(f,n);sum:=0;for k:=1 to n dobeginread(f,a[k]);sum:=sum+a[k];end;close(f);end;Procedure lam;var i,j : integer;Beginfillchar(d1,sizeof(d1),0);fillchar(tr,sizeof(tr),0);d1[0]:=1;d2:=d1;for i:=1 to n dobeginfor j:=0 to sum-a[i] doif (d1[j]=1)and(d2[j+a[i]]=0) thenbegind2[j+a[i]]:=1;tr[j+a[i]]:=i;end;d1:=d2;end;end;Procedure ghif;var m,k : integer;f :text;Beginfillchar(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 dobegins[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àmmộ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ỉ đưathuậ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àngCó 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áncó thể diễn ra đượckhông?Giới hạn: M, N+ 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áchtrả 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áchtrả 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;Beginassign(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;Beginfillchar(D,sizeof(D),0); D[0]:=1;for i:=1 to n dofor j:=m-a[i] downto 0 do inc(D[j+a[i]],D[j]);end;Procedure ghif;Var f :text;Beginassign(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ếtphả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(Nconst 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;Beginfillchar(L1,sizeof(L1),0);L2:=L1;assign(f,fi); reset(f); readln(f,n,k);p:=0;for i:=1 to n dobeginread(f,x);x:=x mod k+k;p:=(p+x)mod k;for j:=0 to k-1 doif (L1[j]>0) thenif (L2[(x+j)mod k]=0)or(L2[(x+j)mod k]>L1[j]+1) thenL2[(x+j)modk]:=L1[j]+1;L2[x mod k]:=1;end;close(f);end;Procedure ghif;var f :text;Beginassign(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ạnphải tìm ra các phần tử cầnloại bỏ. Sau đó đọc lại ...