BÀI TÓAN CHIA KẸO
Trong số báo THNT tháng 8/2003, chuyên mục Đề ra kỳ này, có bài tóan “Chia kẹo”. Nội dung của bài tóan như sau:
Có N gói kẹo, gói thứ i có A[i] cái kẹo.
Yêu cầu: Hãy tìm cách chia các gói kẹo này thành 2 phần sao cho độ chênh lệch giữa tổng số kẹo ở hai phần là ít nhất có thể được 0 <A[i] <1000, 2<=N<=10000
Dữ liệu vào:
Cho trong file Chiakeo.inp: Một dòng duy nhất gồm các giá trị là số kẹo trong mỗi gói, các số cách nhau bởi một dấu cách (N = số gói kẹo đọc được)
Dữ liệu ra:
Ghi ra file Chiakeo.out
<!--[if !supportLists]-->- <!--[endif]-->Dòng 1 lần lượt ghi 3 số: tổng số kẹo ở phần 1, phần 2 và độ chênh lệch giữa hai phần.
<!--[if !supportLists]-->- <!--[endif]-->Dòng 2,3 là giá trị các gói kẹo ở mỗi phần được chia.
Dạng bài tóan này xuất hiện nhiều trong các ứng dụng về lập lịch, nó còn có tên gọi là Number Partitioning. Đây là một bài tóan thuộc lớp NP đầy đủ, không có thuật tóan tốt để giải. Bài viết này xin được trình bày một cách giải Heuristic cho ra kết qủa khá tốt.
Ta phát biểu lại bài tóan: cho n số (trong trường hợp này là số nguyên), tìm cách chia thành 2 phần sao cho độ chênh lệch tổng các số của mỗi phần là ít nhất có thể được
Trước hết chúng ta hãy xem xét một số cách giải:
<!--[if !supportLists]-->1. <!--[endif]-->Duyệt vét cạn
Thuật tóan vét cạn dễ hiểu nhất là xét tất cả các tập con có thể, và trả về tập con có tổng gần với một nửa tổng các số nhất. Nếu có n số, độ phức tạp của thuật tóan sẽ là O(2n) bởi vì một tập n phần tử có 2n tập con. Không gian tính tóan sẽ là O(n). Như vậy cách tiếp cận này không thực tiễn khi n lớn.
Cũng với tư tưởng duyệt vét cạn, bạn có thể cải tiến thành một thuật tóan có độ phức tạp O(2n/2) nhưng ở đây sẽ không bàn kỹ về vấn đề này.
<!--[if !supportLists]-->2. <!--[endif]-->Quy họach động
Thuật giải quy họach động đòi hỏi một mảng bít a[i] có kích thước là tổng các số, a[i]=1 khi và chỉ khi tồn tại tập con có tổng bằng i. Ban đầu, ta khởi tạo mảng a bằng 0, đặt a[0]=1. Sau đó với mỗi số x , quét lại mảng a, và với mỗi phần tử a[i]=1, ta đặt a[i+x]=1. Tiếp tục cho đến khi xét hết dãy số. Không gian tính tóan của thuật giải này phụ thuộc vào tổng các số. Do đó, nó chỉ thực tiễn với các số là số nhỏ, và phải là số nguyên.
<!--[if !supportLists]-->3. <!--[endif]-->Tham lam
Thuật giải tham lam dễ thấy nhất cho bài tóan này như sau: sắp xếp các số theo thứ tự giảm, rồi đặt số lớn nhất vào một trong hai tập. Sau đó, đặt số tiếp theo vào tập đang có tổng bé hơn, tiếp tục cho đến khi tất cả các số được xét.
Thuật giải này cài đặt rất nhanh, nhưng thường cho ra kết qủa không được tốt lắm
Phương pháp Karmarkar-Karp
Dưới đây, chúng ta xem xét một phương pháp Heuristic cho kết qủa khá tốt và cũng không khó cài đặt lắm.
Phương pháp Karmarkar-Karp (KK) đầu tiên sẽ sắp xếp các số theo thứ tự giảm dần. Tại mỗi bước, thuật tóan sẽ lấy hai số lớn nhất phân vào hai phần khác nhau ; mà chưa cần quan tâm là số nào sẽ đi vào tập nào.
Cụ thể, thuật tóan sẽ lọai bỏ hai số lớn nhất, lấy hiệu của chúng – xem đó như một số khác và chèn trở lại vào danh sách đã sắp xếp. Thuật tóan sẽ tiếp tục cho đến khi chỉ còn lại 1 số duy nhất, đó chính là giá trị chênh lệch của hai tập.
Ví dụ, ta có dãy (8; 7; 6 ; 5 ;4 )
Bước
Dãy
Hiệu của 2 số lớn nhất
0
(8; 7; 6 ; 5 ; 4)
8 – 7 = 1
1
(6; 5; 4; 1)
6 – 5 = 1
2
(4; 1; 1)
4 – 1 = 3
3
(3; 1)
3 – 1 = 2
4
(2)
Trong ví dụ này, bạn sẽ thấy phương pháp KK chạy tốt hơn phương pháp tham lam, nhưng vẫn chưa đưa ra được kết qủa tối ưu nhất.
Nếu cần in ra nội dung của mỗi tập, ta cần phải xây dựng 1 cây, với mỗi nút đại diện cho một số trong dãy ban đầu. Mỗi khi phân 2 số lớn nhất vào 2 tập, bạn nối một cạnh giữa 2 nút tương ứng. Cuối cùng, ta sẽ có một đồ thị là một cây bao trùm của các nút ban đầu; sau đó ta sẽ dùng phép tô màu để xác định nội dung của mỗi tập.
Ví dụ, hình dưới đây cho thấy cây được tạo ra từ ví dụ trên. Đầu tiên, nối một cạnh giữa 8 và 7, sau đó nút lớn hơn là 8 bây giờ sẽ thay thế cho hiệu của chúng là 1. Tiếp theo, nối 1 cạnh giữa 6 và 5, thay 6 bởi 1, v.v...
<!--[if !vml]--><!--[endif]-->
Đồ thị tạo thành sẽ tạo thành một cây bao trùm của các nút ban đầu, đó là vì mọi số cuối cùng đều phải được kết hợp, và tổng cộng có n-1 cạnh được tạo ra. Bây giờ chúng ta tô các nút bằng 2 màu, sao cho không có 2 nút kề nào có mầu giống nhau; từ đó nhận ra được các phần tử của mỗi tập được phân chia. Để tô màu, đầu tiên tô một nút tùy ý, sau đó tô tất cả các nút kề với nút này bằng màu còn lại; tiếp tục như vậy, cho đến khi tất cả các nút đều được tô màu.
Trong ví dụ trên, sau khi tô màu, ta nhận được 2 tập con, mỗi tập chứa các nút cùng màu, (7; 4; 5) và (8; 6); cho ta độ chênh lệnh là 2.
Độ phức tạp của thuật tóan là O(n log n) để sắp xếp n số, O(n log n) cho các bước xử lý (bằng cách dùng heap), và O(n) cho bước tô màu. Như vậy tổng cộng độ phức tạp của thuật tóan là O(n log n)
Để giải thích tại sao phương pháp KK Heuristic lại tốt hơn so với thuật giải tham lam thông thường, cần phải có những đánh giá bằng tóan học mà chúng ta sẽ không bàn đến ở đây.
Sau đây là cài đặt của bài tóan JOHNNY (spoj.sphere.pl/problems/JOHNNY), một bài tóan có nội dung hòan tòan giống như bài tóan chia kẹo ở trên.
Để cho gọn, chúng ta chỉ xem qua quy cách input và output của bài tóan:
Input:
Dòng đầu tiên chứa số nguyên n (n<=10000) là số lượng các số trong dãy
N dòng sau, mỗi dòng chứa một số nguyên dương bé hơn 10^14.
Output:
In ra số thứ tự của các số thuộc 1 trong 2 tập (tập nào cũng được) mà ta phân chia, mỗi số trên một dòng.
Scoring
Số điểm bạn nhận được là log10(s/|d|+1) , trong đó s là tổng các số, còn d là chênh lệch giữa hai phần mà chương trình của bạn chia ra.
Ví dụ:
Input mẫu:
3
5
8
4
Output mẫu:
2
3
Bạn sẽ được số điểm là log10((5+8+4)/(8+4-5)+1))=0.327 điểm
Chương trình sau chạy trên nền Free Pascal; với chương trình này bạn có thể nhận được trên 17 điểm:
program johnny;
const finp='johnny.inp';
fout='johnny.out';
type
theap = record
sz:integer;
hh:array[1..10000] of integer;
end;
pnode = ^tnode;
tnode = record
v:integer;
next:pnode;
end;
llist = pnode;
var
tree:array[1..10000] of llist;
a,b:array[1..10000] of int64;
z:array[1..10000] of integer;
sum:array[0..1] of int64;
g:array[1..10000] of shortint;
d:int64; n:integer; h:theap;
procedure llist_insert(var l:llist; v:integer);
var p:pnode;
begin
new(p); p^.v:=v;
p^.next:=l; l:=p;
end;
procedure heapify(var h:theap; i:integer);
var l,r,j,t:integer;
begin
with h do
begin
l:=i shl 1; r:=i shl 1 + 1;
if (l<=sz) and (b[z[hh[l]]]>b[z[hh[i]]]) then
j:=l else j:=i;
if (r<=sz) and (b[z[hh[r]]]>b[z[hh[j]]]) then
j:=r;
if j<>i then
begin
t:=hh[i];
hh[i]:=hh[j];
hh[j]:=t;
heapify(h,j);
end;
end;
end;
procedure insert(var h:theap; k:integer);
var i:integer;
begin
with h do
begin
inc(sz);
i:=sz;
while (i>1) and (b[z[hh[i shr 1]]] < b[z[k]]) do
begin
hh[i]:=hh[i shr 1];
i:=i shr 1;
end;
hh[i]:=k;
end;
end;
procedure extractmax(var h:theap; var k:integer);
begin
with h do
begin
k:=hh[1];
hh[1]:=hh[sz];
dec(sz);
heapify(h,1);
end;
end;
procedure qsort(l,r:integer);
var i,j:integer;
p,t:int64;
begin
i:=l; j:=r; p:=a[z[(l+r) div 2]];
repeat
while a[z[i]]<p do inc(i);
while p<a[z[j]] do dec(j);
if i<=j then
begin
t:=z[i];
z[i]:=z[j];
z[j]:=t;
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
function str264(s:string):int64;
var code:integer;
begin
val(s,str264,code);
end;
procedure nhap;
var i:integer;
s:string;
begin
readln(n);
for i:=1 to n do
begin
readln(s);
a[i]:=str264(s);
z[i]:=i;
end;
end;
procedure chianhom;
var i,k1,k2:integer;
begin
b:=a;
for i:=n downto 1 do
insert(h,i);
for i:=1 to n-1 do
begin
extractmax(h,k1);
extractmax(h,k2);
llist_insert(tree[k1],k2);
llist_insert(tree[k2],k1);
b[z[k1]]:=b[z[k1]]-b[z[k2]];
insert(h,k1);
end;
end;
procedure tomau;
var q:array[1..10000] of integer;
x,y:integer;
i, top: integer;
p: pnode;
begin
for i:=1 to n do g[i]:=-1;
fillchar(sum,sizeof(sum),0);
x:=1; y:=1;
q[1]:=1; g[1]:=0;
sum[0]:=a[z[1]];
while x<=y do
begin
top:=q[x];
p:=tree[top];
inc(x);
while p<>nil do
begin
if g[p^.v]=-1 then
begin
inc(y);
q[y]:=p^.v;
g[p^.v]:=1-g[top];
inc(sum[g[p^.v]],a[z[p^.v]]);
end;
p:=p^.next;
end;
end;
end;
procedure xuly;
begin
qsort(1, n);
chianhom; tomau;
end;
procedure inkq;
var i:integer;
begin
for i:=1 to n do
if g[i]=0 then
writeln(z[i]);
end;
begin
assign(input, finp);
reset(input);
assign(output, fout);
rewrite(output);
nhap; xuly; inkq;
close(input);
close(output);
end.
Trên đây chỉ là bài tóan chia kẹo ở dạng đơn giản nhất (phân chia thành 2 tập). Bài tóan này còn có thể mở rộng hơn nữa; rất mong được có dịp trao đổi thêm cùng với các bạn.
Trang Chính 
Calendar
Tiêu đề: BÀI TÓAN CHIA KẸO 
