Bài toán chia kẹo

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á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