Разложить камни в 2 кучи так, что разность весов двух куч была минимальной - Pascal
Формулировка задачи:
Разложить камни в 2 кучи так, что разность весов двух куч была минимальной.
Вот мой вариант, однако, неправильный:
Где ошибка?
Кстати, 1<n<20 и 1<w[i]<100 000.
type list = array[1..21] of longint; var n,i,w1,w2,d:integer; w:list; begin read(n); d:=0; For i:=1 to n do read(w[i]); If n=1 then begin write(w[1]); halt; end; For i:=1 to n div 2 do begin If w1>w2 then w2:=w2+abs(w[i+d]-w[i+d+1]) else w1:=w1+abs(w[i+d]-w[i+d+1]); d:=d+1; end; If n mod 2=0 then write(abs(w1-w2)) else write(w[n]-abs(w1-w2)); end.
Решение задачи: «Разложить камни в 2 кучи так, что разность весов двух куч была минимальной»
textual
Листинг программы
uses crt;
var a: array [1..101] of real;
gr1,gr2,tmp: real;
i,j,n: integer;
begin
clrscr;
write('Количество камней: ');
readln(n);
writeln('Вес каждого: ');
for i:=1 to n do
readln(a[i]);
for i:=1 to n do
for j:=1 to n do
if a[i]>a[j] then
begin
tmp:=a[i];
a[i]:=a[j];
a[j]:=tmp;
end;
gr1:=a[1];
gr2:=a[2]+a[3];
writeln('Группа 1: ',a[1]:5:2);
writeln('Группа 2: ',a[2]:5:2);
writeln('Группа 2: ',a[3]:5:2);
i:=4;
while i<=n do
begin
if gr1>=gr2 then
begin
gr2:=gr2+a[i];
writeln('Группа 2: ',a[i]:5:2);
end
else
begin
gr1:=gr1+a[i];
writeln('Группа 1: ',a[i]:5:2);
end;
inc(i);
end;
writeln;
writeln('Итого: Группа 1: ',gr1,' Группа 2: ',gr2);
readln;
end.
Объяснение кода листинга программы
- Создается переменная
n, которая хранит количество камней. - Пользователю предлагается ввести вес каждого камня. Введенные значения сохраняются в массиве
a. - Для каждого камня в массиве
aпроисходит сравнение его веса с весом всех остальных камней. Если текущий вес больше максимального, то он заменяет максимальный вес. - Создаются две переменные
gr1иgr2, которые будут хранить вес групп камней. - Инициализируется переменная
iравной 1, а переменнаяjравной 2. - Пока
iменьше или равноn, выполняется цикл. - Внутри цикла проверяется, какой из весов (
gr1илиgr2) больше. - Если
gr1большеgr2, тоgr2увеличивается на вес текущего камня, а также выводится информация о группах камней. - Если
gr1меньше или равноgr2, тоgr1увеличивается на вес текущего камня, а также выводится информация о группах камней. - После завершения внутреннего цикла,
gr1иgr2выводятся на экран вместе с общим количеством камней.