Bài toán chia nhóm trong Pascal

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;