[Tin học]- Bài Toán Chia Kẹo

[thanhthuytu]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Chia kẹo
Có N gói kẹo, gói thứ i có A cái kẹo.
Yêu cầu: Hãy tìm cách chia các gói kẹo này thành 2 phần sao cho độ chênh lệch giữa tổng số kẹo ở hai phần là ít nhất có thể được 0 <A <1000, 2≤N≤10000
Dữ liệu vào:
Cho trong file Chiakeo.inp: Một dòng duy nhất gồm các giá trị là số kẹo trong mỗi gói, các số cách nhau bởi một dấu cách (N = số gói kẹo đọc được)
Dữ liệu ra:
Ghi ra file Chiakeo.out
- Dòng 1 lần lượt ghi 3 số: tổng số kẹo ở phần 1, phần 2 và độ chênh lệch giữa hai phần.
- Dòng 2,3 là giá trị các gói kẹo ở mỗi phần được chia.

Ví dụ:
Chiakeo.inp
3 4 7 12

Chiakeo.out
14 12 2
3 4 7
12

 

[thanhthuytu]

Dưới đây là cho trường hợp chênh lệch ít nhầt.

const fi='input.txt'; fo='output.txt';
nmax=100;
var a,b:array[1..nmax] of integer;
chk:array[0..20000] of boolean;
luu:array[1..20000] of byte;
tong:integer;
f:text;
n:byte;

procedure readf;
var k:byte;
begin
assign(f,fi); reset(f);
readln(f,n);
for k:=1 to n do read(f,a[k]);
close(f);
for k:=1 to n do b[k]:=a[k];
end;

procedure truy(i:integer);
begin
if i<>0 then
begin
truy(i-a[luu[i]]);

a[luu[i]]:=-1;
end;
end;

procedure xuly;
var k:byte;
i,mid:integer;
begin
tong:=0;
fillchar(chk,sizeof(chk),false);
chk[0]:=true;
for k:=1 to n do
begin
for i:=tong downto 0 do
if chk[i] then
if not chk[i+a[k]] then
begin
chk[i+a[k]]:=true;
luu[i+a[k]]:=k;
end;
inc(tong,a[k]);
end;
mid:=tong div 2;
while not chk[mid] do dec(mid);
assign(f,fo); rewrite(f);
writeln(f,tong-2*mid);
truy(mid);
writeln(f);
for k:=1 to n do
if a[k]>=0 then write(f,a[k],' ');
writeln(f);
for k:=1 to n do if a[k]<0 then write(f,b[k],' ');

close(f);
end;

begin
readf;
xuly;
end.

 

[tomatoblack]

bạn có thế nói rõ thuật toán của bài này một chút được hông?

 

[p_trk]

quay lại bài toán chia kẹp một tí ! nhờ anh Thành và bạn Hưng giải thích giúp mình rõ thuật toán chia kẹo này được k ! cảm ơn nhiều ạ !!! (*)

 

[p_trk]

thấy mấy anh pro trường em nói qhd được nhờ anh Thành và Hưng giải thích giúp em công thức qui hoạch động !!! (*)