Giải bài toán chia kẹo trong PasCal
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (134.57 KB, 10 trang )
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ó A
i
cá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ố A
i
(i=1, 2,.., N; A
i
<=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 s
i
=1 thì gói thứ i thuộc phần 1, nếu s
i
=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 A
i
/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àx
1
, x
2
,.., x
t
vậy thì đến
bước này sẽ có thểsinh ra các tổng x
1
, x
2
,.., x
t
và A
i
và x
1
+A
i
,x
2
+A
i
,..,x
t
+A
i
.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 d
1
, d
2
,.., d
N
. Người bánhàng có M đồng
tiền b
1
, b
2
,.., b
m
. 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à d
i
,b
j
<=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 W
i
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ố W
i
>= 0 thì đây là một bài toán chia kẹo. Để các số W
i
không âm tachỉ cần
đảo lại các thanh mà W
i
< 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 A
1
,A
2
,.., A
N
. 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.
