Реализация нерекурсивного алгоритма
program pohod; const nnn = 100; {максимально возможное количество различных весов} var f: text; d,razn,k,i,j,n: integer; sum: longint; ves,kol: array[1..nnn] of word; take, dif: array[0..nnn] of word;
procedure vyvod(a: integer); begin writeln(a); halt; {принудительное завершение работы программы} end;
begin {---- Ввод данных и их сортировка ---} ... {---- Основная часть программы -----} d:= sum mod 2; {показатель четности общего веса} sum:=(sum div 2)+ d; {"большая половина" общего веса}
dif[0]:= sum; razn:= sum; for i:= 1 to k do begin take[i]:= min(dif[i-1] div ves[i],kol[i]); dif[i]:= dif[i-1]- take[i]*ves[i]; if dif[i]< razn then razn:= dif[i]; if razn <= d then vyvod(d); {проверка того, что уже на первом шаге найдено решение} end;
{---- Заполнение массива --------} i:= k; while i>0 do begin if take[i]= 0 then i:= i-1 {переход к следующей компоненте} else begin dec(take[i]); уменьшение текущей компоненты на 1} inc(dif[i],ves[i]); {увеличение остатка на соотв. величину} for j:= i+1 to k do {перезаполнение хвоста} begin take[j]:= min(dif[j-1] div ves[j],kol[j]); dif[j]:= dif[j-1]- take[j]*ves[j]; if dif[j]< razn then razn:= dif[j]; if razn <= d then vyvod(d); {проверка результата} end; i:= k; end; end; vyvod(2*razn-d); end.
