Thuật toán chia kẹo và ứng dụng giải lớp bài toán chia nhóm
Lã Thành Công
Xét một bài toán chianhóm tổng quát như sau:
Chon số a1, a2,...,an (n 'NI*) và m số b1, b2,..., bm (m < n,m ' NI*).
Yêucầu: Hãy chia n số a1, a2,..., an thành m nhómsao chotổng các phần tử của nhóm i bằng bi (i = 1,m).
Trướckhi đưa ra phương pháp giải bài toán trên ta xét bài toán đơn giản nhưng thú vịđó là bài "chia kẹo":
Có n gói kẹo mỗi góicóai cái kẹo (i= 1,n). Hãytìm cách chia n gói kẹo thành 2 nhóm sao cho chênh lệch giữa 2 nhóm là ít nhất.
Bài toán có thể giảitheo thuật toán sau:
Tađi xây dựng các tổng có thể có được từ gói kẹo. Ta thấy nếu tổng nào gồm (n div2) nhất thì đó là giá trị của nhóm 1. Phần còn lại sẽ thuộc vào nhóm 2. Để xâydựng được ta làm như sau:
Tadùng 3 mảng làm các công việc sau:
Mảng A dùng để ghi lại các giá trị của tổng
Mảng B dùng để ghi lại các phần tử cuối cùng cho vàođể đạt giá trị ở A.
Mảng C dùng để ghi lại các vị trí của tổng mà khôngcó phần tử ở B. Mảng này dùng để lần lại các phần tử có để đạt giá trị ở A.
Thựchiện như sau:
A[0]:=0; Max := 0; B [0]:= 0; C [0]:= 0;
Fori:= 1 to n do
For j:= 0 to max do
Begin
D:= True; m:= max;
For k:= 0 to max do if (A[j] +ai)= A[k] then D:= false;
If D then
Begin
inc (m);
A[m] := A[j] + ai;
B[m] := i;
C[m] := j;
end;
Thuậtgiải trên đã xây dựng được các tổng có thể có từ n gói kẹo. Khi chọn được A[i]gần với ( n div 2) nhất thì ta thực hiện thủ tục lần ngược như sau:
Fillchar(Logic, size of (logic), false);
WhileA[i] > 0 do
Begin
Logic [B[i]] := true; (cho phần tửB[i] vào nghiệm)
i:= c[i];
End;
Khiđó các phần tửmang giá trị Logic làtrue sẽ tạo thành một nhóm có tổng A[i] ban đầu.
Xéttiếp một bài toán ở mức độ cao hơn như sau:
Cho n số a1, a2,..., an(n ' NI*).
Tìmcách chia số trên thành m nhóm sao chomỗi nhóm đều có tổng bằng nhau và m tìm được là lớn nhất.
Cách giải : Bài toán trên ta có thể duyệtmọi m là ước số của T = Σ ai. Mà ở đó m chạytừ T về 1.
Vớimỗi m có được ta có tổng các nhóm sẽ là D =T/m. Với mỗi dự tuyển (m,D):
