Иллюстрация

Реализация нерекурсивного алгоритма

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.

Наиболее понятным образом принцип работы нашей программы можно продемонстрировать на примере.

Вес
Количество

Пусть имеется семь предметов (n = 7) с весами 9, 5, 25, 11, 9, 5, и 11 единиц (килограмм, фунтов, бушелей...). Тогда всего есть четыре разных вида предметов (k = 4).

Общая сумма весов равна 75; следовательно, "большая половина" sum = 38. Теперь нужно найти такой набор предметов, чей суммарный вес будет наиболее близким к этой "золотой середине". Кроме того, не стоит забывать и о сделанном ранее замечании: как только найдется набор, вес которого отличается от "золотого" лишь на единицу, поиск можно закончить.

Начнем теперь заполнять массивы take и dif (массив dif хранит остатки, в пределах которых можно проводить дальнейшие вычисления).

На начальном ("нулевом") шаге мы заполним массив take так, чтобы в создаваемый набор попали по возможности самые тяжелые предметы (см. раздел реализации "Основная часть программы"). Таким образом, получим следующие состояния массивов:

ves	-
take
dif

После этого шага переменная razn, которая хранит отклонение текущего набора весов от оптимального, будет содержать значение 2. Попытаемся уменьшить это значение (переход к разделу реализации "Заполнение массива").

Двигаясь от конца массива take к его началу, будем уменьшать поочередно каждую его ненулевую компоненту. Разумеется, при этом будут возникать изменения в хвосте этого массива; эти изменения мы будем вносить туда в обычной последовательности "от начала к концу".

Таким образом, наши массивы последовательно примут следующие значения (некоторые непринципиальные шаги опущены):

ves	-
take
dif

ves	-
take
dif

ves	-
take
dif

ves	-
take
dif

ves	-
take
dif

ves	-
take
dif

ves	-
take
dif

ves	-
take
dif

ves	-
take
dif

ves	-
take
dif

ves	-
take
dif

ves	-
take
dif

Итак, мы убедились в том, что найденное в самом начале значение переменной razn и было минимальным (найденные группы весов соответственно 25 + 11 = 36 и 11 + 9 + 9 + 5 + 5 = 39). Необходимо отметить, что из приведенных выше таблиц видно (см. шаг 5), что существует еще один способ разделить приведенный набор весов таким же оптимальным образом: (11 + 11 + 9 + 5 = 36 и 25 + 9 + 5 = 39). Найденная разница 39 - 36 = 3 и будет окончательным результатом, который программа сообщит пользователю.

Дата добавления: 2014-01-03