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ố a
1
, a
2
,...,a
n
(n 'NI*) và m số b
1
, b
2
,..., b
m
(m < n,m ' NI*).
Yêucầu: Hãy chia n số a
1
, a
2
,..., a
n
thành m nhómsao chotổng các phần tử của nhóm i bằng
b
i
(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óa
i
cái kẹo (i= 1,n). Hãytìm cách chia n gói kẹo thành 2 nhóm sao

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ố a
1
, a
2
,..., a
n
(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 = Σ a
i
. 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):
Khiđó ta sẽ dùng thuật toán trên để tìm m nhóm có tổng là D.
+Lưu ý một điều đó là:
Taphải sắp xếp a
i
(i=1,n) theo thứ tự giảm dần để khi duyệt ta đượckết quả tối ưu.
Tasẽ dùng thuật toán trên tìm lần lượt m nhóm tổng là D. Mỗi lần tìm được mộtnhóm ta sẽ
nhấc các phần tử thuộc nhóm đó ra và thực hiện lại với các phần tửcòn lại.
Khi tìm được một dựtuyển (m,D) thoả mãn thìđó sẽ là tốiưu của lời giải.

tiếp theo làthông tin về các khách được trả tiền theo quy ước giống câu 1.