Cho n túi kẹo, túi thứ i có ai viên. Hãy chia các túi này thành hai phần sao cho số viên kẹo chênh lệch giữa hai phần là nhỏ nhất
Ví dụ: Cho 7 túi có số viên kẹo trong từng túi lần lượt là: 30, 25, 40, 20, 26, 30, 20.
Sau khi chia thành 2 phần để có số viên kẹo chênh lệch giữa 2 phần nhỏ nhất ta được kết quả:
Phần thứ nhất:30 + 25 + 40 = 95
Phần thứ hai:20 + 26 + 30 + 20 = 96
Vậy số viên chênh lệch nhỏ nhất là: 96 –95 = 1
Dữ liệu vào:Cho file CHIAKEO.INP gồm:
-Dòng đầu tiên chứa số n là số lượng các túi kẹo.
-n dòng tiếp theo, dòng thứ i chứa số viên của túi kẹo thứ i.
Kết quả: Ghi ra file CHIAKEO.OUT một số nguyên là số viên chênh lệch nhỏ nhất.
uses crt;
var d:text; n,i,min,t1,t2:longint; a,b:array[1..100000]of longint;
procedure xuly;
var i:longint;
begin
t1:=0;
t2:=0;
for i:=1 to n do if b[i]=0 then inc(t1,a[i]) else inc(t2,a[i]);
if min>abs(t1-t2) then min:=abs(t1-t2);
end;
function dequy(a:longint):longint;
var i,j:longint;
begin
for i:=0 to 1 do
begin
b[a]:=i;
if a<>n then dequy(a+1);
if a=n then begin dequy:=1; xuly; end;
end;
end;
begin
clrscr;
assign(d,’input.pas’);reset(d);
readln(d,n);
for i:=1 to n do read(d,a[i]);
close(d);
assign(d,’output.pas’);rewrite(d);
min:=high(longint);
dequy(1);
writeln(d,min);
close(d);
end.
/////////////////////
Một số txt cho bạn tham khảo:
const fi=’chiakeo.inp’;
fo=’chiakeo.out’;
var s,i,n,s1,j,min,c1:longint;
a:array[0..100000000]of longint;
f,g:text;
begin
assign(f,fi); reset(f);
assign(g,fo); rewrite(g);
readln(f,n);
for i:=1 to n do
read(f,a[i]);
s:=0; min:=999999999;
for i:=1 to n-1 do
begin
s:=s+a[i]; s1:=0;
for j:=i+1 to n do
s1:=s1+a[j];
if abs(s-s1)<min then begin
c1:=i;
min:=abs(s-s1);
end;
end;
write(g,min);
close(f); close(g);
end.