Bài toán Chia kẹo

[HLN1994]

Đề bài: 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
- 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.
- 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:

1.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.

2.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.

3.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 )




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

Đồ 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 toán:

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.
Nguồn từ: http://chuyenhvt.net

Các bài viết cùng chuyên mục:

• Vmo 2012
• Các bạn giải giúp mình nhé
• Ai pro toán thì giúp mình nhé!
• Báo toán học và tuổi trẻ số 315 năm 2003
• Tài liệu ôn thi quốc gia
• Đề thi Môn Toán Khối B - Kì thi Đại Học 2011
• Đề thi Môn Toán Khối D - Kì thi Đại Học 2011
• Đề thi Môn Toán Khối A - Kì thi Đại Học 2011
• Các hàm số lượng giác
• Đề thi HSGQG Môn Toán 2011

[Mr.Pit]

sao mềnh chả bao h nhớ tên thuật toán nhờ??
Nguồn từ: http://chuyenhvt.net

[trungeck]

Cái bài giải này hay đấy nhỉ .....,,,,,,,,,,,,,,
Nguồn từ: http://chuyenhvt.net

[Sevlyorum]

Chép code mà hình như lại còn "Việt" hóa 1 số ctcon
Nguồn từ: http://chuyenhvt.net

[HLN1994]

P/s: Mình muốn nói thêm về phần Quy Hoạch Động (QHĐ) một chút:
Việc QHĐ của bài toán này dựa vào một trong những bài toán cơ bạn nhưng mang tính chất kinh điển của thuật toán QHĐ.Mình xin giới thiệu thêm qua đoạn chương trình chính của thuật toán QHĐ trong bài toán Chia kẹo trên:

procedure QHD;
Var i,j,Max,Tmax,T:longint;
Begin
     S:=0;
     S1:=0;
     L[0]:=1;
     Tmax:=0;
     Min:=MaxInt;
     for i:=1 to K do S:=S+P[i];
     for i:=1 to K do
     Begin
          Max:=Tmax;
          for T:=Tmax downto 0 do
          Begin
               if (L[T]<>0) and (L[T+P[i]]=0) and (T+P[i]<=S) then
               Begin
                    L[T+P[i]]:=i;
                    j:=T+P[i];
                    if Abs(S-2*j)<Min then
                    Begin
                         Min:=Abs(S-2*j);
                         S1:=j;
                    End;
                    if Min=0 then exit;
               End;
               if T+P[i]>Max then Max:=T+P[i];
          End;
          TMax:=Max;
     End;
end;

Mong nhận được sự đóng góp của mọi người
Nguồn từ: http://chuyenhvt.net

[lineker]

Good, Nhưng nếu là lập trình từ từ hẵng viết vào ngôn ngữ pascal. Lập trình viên quan trọng nhất là ý tưởng sau mới đến thực hiện. Khi giải một bài toán nào đó bằng ngôn ngữ lập trình thì đã là khó rồi (Vì pascal, VB hay bất cứ ngôn ngữ nào cũng bắt từng dấu ";" một ) thế nên để giảng lại một bài lập trình lại là vấn đề khó khăn hơn nữa mà trong trường hợp này người ta dùng giả mã (hay còn gọi là giả ngôn ngữ). Việc này có ba tác dụng thứ nhất làm đơn giản hóa và dễ hình dung cho người đọc (ngay cả trong trường hợp người đó không hiểu biết về lập trình nhiều lắm). Thứ hai kết tụ rất nhiều các trường phái của những ngôn ngữ khác nhau để giải bài toán tìm ra một cách tối ưu nhất. Cụ thể trong trường hợp này Quý thuộc trường phái php trong khi bạn viết ngôn ngữ bằng pascal thì quý sửa lỗi cho bạn vào mắt ^^ thứ 3 là tránh những kẻ lười Nhân ạ đây là một bài toán ko phổ biến chứ nếu ngày xưa hồi Q học năm thứ nhất mà bạn post mấy bài kiểu tính tiền điện hay giải phương trình thì sẽ bị người dùng copy gọn mặc dù sau khi chạy ngon lành và trình lên thấy giáo họ chả hiểu cái quái gì cả. Thêm một lý do nữa là bảo vệ bản quyền cho chú đấy Nhân ạ.

Ví dụ về giả mã thay bằng for (i=0;i<100;i++) trong ngôn ngữ thật thì là for (từ 1 cho đến 100)
Nguồn từ: http://chuyenhvt.net