Bài toán chia nhóm 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 (82.97 KB, 4 trang )
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
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] +a
i
)= A[k] then D:= false;
If D then
Begin
inc (m);
A[m] := A[j] + a
i
;
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ố 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.
Nếu ta không sắp xếp a
i
(i=1, n) theo thứ tự giảm dần thì ta sẽ thấy trường hợp sau bị vướng
mắc:
VD:dãy n số là: n = 7
8 2 1 3 9 10 11
Tathấy m
max
không sắp xếp thì lần đầu máy sẽ cho (8,2,1)vào một nhóm và như vậy không
làm tiếp được.
Qua2 ví dụ ta đã phần nào hiểu được ưu thế của thuật toán trên trong một lớp cácbài toán
chia nhóm, một lớp bài toán mà nếu không có thuật toán và nắm bắt bảnchất ta sẽ rất khó
giải.
Tuynhiên có thể còn nhiều thuật toán khác hay hơn mà tôi chưa biết. Tôi hy vọngcác bạn
có thểtìm ra nhiều nhiều thuậttoán hay hơn.
Đểluyện tập, tôi xin đưa ra một bài toán sau (Thi chọn đội tuyển quốc gia năm1995):
Mộtquầy trả tiền có n loại tiền với mệnh giá (giá trị tiền ghi trên tờ tiền)làA[1], A[2],...
A[n] (các A[i]lànguyên dương và khác nhau từng đôi).Giả thiết loại tiền mệnh giá A[i] có
B[i] tờ (i := 1, n). Có M khách (đánh sốhiệu tử 1 -> m) cần lấy tiền. Số tiền khách i cần lấy
là K[j], K[j] nguyêndương, 1 <= j <= một. Quy định rằng với mỗi khách hoặc quầy từ chối
trảtiền hoặcphải trả đúng số tiền màkhách cần lấy.
Dữliệu vào file INP.TXT dòng đầu ghi giá trị N (N <= 10), dòng tiếp theoghi các giá trị
A[1], A[2],..., A[n] dòngtiếp theo ghi các giá trị B[1], B[2],..., B[n]. Sau đó là dòng ghi giá
trị Mvà dòng ghi các giá trị K[1], K[2], K[3]..., K[M]. Tất cả đều nguyên dương.
Yêucầu:
Tìm cách trả sao cho trảđược nhiều khách nhất. Thông báo ra file OU1.TXT, trong
dòngđầu ghi số khách được trả tiền, trong cácdòng tiếp theo mỗi dòng ghi thông tin về một
khách, số tiền phải trả và dãy cácsố X[1], X[2],..., X[n] trong đó X[i] là số tờ của loại tiền
mệnh giá A[i] (1<=i <= n) được trả cho khách.
Tìm cách trả sao cho trảđược nhiều tiền nhất. Thông báo ra file OU2.TXT số tiền dòng đầu
tiếp theo làthông tin về các khách được trả tiền theo quy ước giống câu 1.
