An và Bình là hai anh em. Ba của An sau chuyến đi công tác xa nhà trở về, mua cho An và Bình ~N~ gói kẹo, gói thứ ~i~ có ~A_i~ viên kẹo.

Để tránh việc tranh giành kẹo lẫn nhau, ba của An đã thống nhất việc chia kẹo theo cách sau:

• Trước hết, ba của An chọn ra một số nguyên ~k~ (với ~1 ≤ k ≤ N~).
• An sẽ được chia các gói kẹo từ ~1~ đến ~k~. Phần còn lại (các gói kẹo từ ~k + 1~ đến ~N~) sẽ được chia cho Bình.

Để tránh sự phân bua giữa hai anh em, ba của An muốn lựa chọn chỉ số ~k~ sao cho chênh lệch giữa tổng số lượng viên kẹo của hai anh em là nhỏ nhất có thể. Hãy giúp ông thực hiện điều này.

Có N gói kẹo được đánh số hiệu từ 1 đến N . Gói kẹo thứ i ( i = 1,2,3,...,N) có Ai chiếc kẹo . Cần phân chia N gói kẹo thành 3 phần :

• Phần 1 gồm các gói kẹo 1,2,...,i . Tổng số chiếc kẹo của phần 1 là x = A1 + A2 + ... + Ai;
• Phần 2 gồm các gói kẹo i + 1 , i + 2 , ... , j . Tổng số chiếc kẹo của phần 2 là y = Ai+1 + Ai+2 + ... + Aj ;
• Phần 3 gồm các gói kẹo j + 1 , j + 2 , ... , N . Tổng số chiếc kẹo của phần 3 là z = Aj+1 + Aj+2 + ... + An ;

Với 1 < i < j < N .​

Yêu cầu : Tìm cách phân chiaN gói kẹo sao cho chênh lệch giữa phần có tổng số kẹo nhiều nhất và phần có tổng số kẹo ít nhất là nhỏ nhất , tức là max ( x , y , z ) - min ( x , y , z ) đạt giá trị nhỏ nhất . Ta đặt giá trị T = max ( x , y , z ) - min ( x , y , z ).

Dữ liệu cho trong tệp văn bản ChiaKeo.Inp gồm :

• Dòng thứ nhất ghi số nguyên dương N là số gói kẹo .

Dòng thứ hai ghi N số nguyên dương A1 , A2 , ... , An ( 1 < Ai < 103 ) là số chiếc kẹo của N gói kẹo . Các số ghi trên một dòng cách nhau bởi dấu cách .

Nội dung Text: Thuật toán chia kẹo

1. 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
2. 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;
3. 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
4. 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.

5. 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
6. + 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;
7. 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.
8. 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
9. 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;
10. 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.