5. Kỹ thuật đánh dấu

 5. Kỹ thuật đánh dấu
Để không xét lại những phần tử đã duyệt, người ta thường đánh dấu các phần tử đã
duyệt.
Ví dụ khi thực hiện thuật toán sàng Eratosthenes, để tìm các số nguyên tố không
vượt quá số nguyên dương N, chúng ta đánh dấu trên trục số các bội của 2, rồi các bội của 3
chưa đánh dấu, các bội của 5 chưa đánh dấu,…. Các số còn lại chưa bị đánh dấu chính là các
số nguyên tố.
Ví dụ 1. Chia kẹo
Có n gói kẹo (n200), các gói kẹo được đánh số từ 1 đến n. Gói kẹo thứ i có Ai cái kẹo
(1i n, 0< Ai 200). Hãy xếp các gói kẹo thành hai phần sao cho tổng số kẹo của hai phần
chênh lệch nhau ít nhất.
Input cho trong File văn bản CHIAKEO.IN
Dòng thứ nhất ghi số n,
Các dòng sau ghi lần lượt các giá trị từ A1 đến An
Output.
Kết quả ghi ra file văn bản CHIAKEO.OUT
Dòng thứ nhất ghi số kẹo chênh lệch giữa hai phần,
Dòng thứ hai ghi số hiệu các gói kẹo thuộc phần thứ nhất,
Dòng thứ ba ghi số hiệu các gói kẹo thuộc phần thứ hai.
Các số cách nhau ít nhất một dấu trống.
Phân tích.
Dùng một trục số với các điểm chia nguyên từ 0 đến 40000 để đánh dấu các tổng số
kẹo có thể sinh ra khi gộp một số gói kẹo nào đó lại với nhau. Ta lần lượt xét từng gói kẹo từ
gói A1 đến gói An. Giả sử bây giờ xét đến gói Ai , để tạo ra các tổng mới ta cộng Ai vào từng
tổng đã có (cộng từ tổng lớn nhất về tổng nhỏ nhất là 0)
Mỗi khi sinh ra một tổng mới, cần ghi lưu số hiệu gói kẹo vừa gộp vào để sinh ra tổng
mới này.
Từ điểm X là điểm nửa tổng tất cả số kẹo (nếu X đã đánh dấu) hoặc điểm đánh dấu
gần điểm X nhất (nếu điểm X không được đánh dấu) biết được gói cuối cùng vừa cho vào
một phần, trừ đi số kẹo của gói này ta đến tổng mới (điểm đánh dấu mới) và lại biết số hiệu
gói kẹo nào vừa gộp vào để tạo ra tổng mới này…quá trình kết thúc khi đi đến điểm đánh
dấu 0.
Ví dụ. Có 5 gói kẹo với số kẹo lần lượt là: A1= 3, A2=15, A3=2, A4=6, A5=19. Tổng tất cả
các gói có số kẹo là 45. Hy vọng rằng một phần sẽ là 23. Nếu không, cần chọn số kẹo một
phần là số gần với số 23 nhất. Số này phải là tổng có thể sinh ra do xếp một số gói kẹo lại với
nhau.
Đầu tiên chưa xét gói kẹo nào thì tổng là 0.
Xét gói A1: có tổng mới là 3
Xét các gói A1 và A2: các tổng mới có thể sinh ra là: 15+3=18, 15+0=15, và tổng cũ là 3.
Xét các gói A1, A2 và A3: các tổng mới có thể sinh ra là: 2+18=20, 2+15=17, 2+3=5 (đã
có trước), 2+0=2, và các tổng cũ là 18, 15, 3
Xét các gói A1, A2, A3 và A4 tương tự sẽ đánh dấu thêm các tổng: 7, 9, 21, 23, 24, 26
Đến đây thấy đã xuất hiện tổng một số gói kẹo là 23. Tìm ngược lại quá trình sinh ra
tổng 23 ta được đáp số: Một phần sẽ gồm các gói kẹo A4, A3, A2, phần thứ hai gồm các gói
kẹo còn lại.
Văn bản chương trình
Program chiakeo;
const fi = 'chiakeo.in';
fo = 'chiakeo.out';
maxn = 200;
maxk = 200;
maxs = 40000;
type m1 = array[0..maxs] of byte;
m2 = array[1..maxn] of byte;
var a : m2;
t : m1;
sum : word;
n : byte;
Procedure nhap;
var f: text;
i: byte;
begin
sum:= 0;
assign(f,fi); reset(f);
readln(f,n);
for i:=1 to n do
begin
read(f,a[i]);
sum:= sum + a[i];
end;
close(f);
end;
Procedure danhdau;
var i: byte; max,j: word;
begin
fillchar(t,sizeof(t),0);
t[0]:= 1;
max := 0;
for i:=1 to n do
begin
for j:=max downto 0 do
if t[j]>0 then
if t[j+a[i]]=0 then
t[j+a[i]]:=i;
max:= max + a[i];
end;
end;
Procedure timkq;
var i,tong: integer;
f : text;
kq : m2;
begin
fillchar(kq,sizeof(kq),0);
assign(f,fo);
rewrite(f);
tong:= sum div 2;
while t[tong]=0 do
dec(tong);
writeln(f,sum–tong–tong));
repeat
kq[t[tong]]:= 1;
tong:= tong – a[t[tong]];
until tong=0;
for i:=1 to n do
if kq[i] = 0 then write(f,i,' ');
writeln(f);
for i:=1 to n do
if kq[i] = 1 then write(f,i,' ');
close(f);
end;
BEGIN
nhap;
danhdau;
timkq;
END.