Полный перебор с отсечением

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

Рекурсивный алгоритм

Пример сравнения рекурсивного и нерекурсивного алгоритма

Задача. Двое друзей решили пойти в поход, собрали и взвесили все необходимые вещи. Как им разделить набор предметов на две части наиболее честным образом?

(Имеется набор натуральных чисел, быть может, с повторениями. Необходимо разделить его на два поднабора так, чтобы разность сумм весов была минимальной.)

Нужно перебрать все возможные подмножества заданного набора весов. Для решения этой задачи существует несколько классических алгоритмов, мы воспользуемся простейшим, который носит название "полный перебор". В полном соответствии со своим названием, этот алгоритм перебирает все возможные варианты наборов.

program pohod_rec;var f: text; a: array[1..100] of integer; n: integer; min,obsh_ves: longint;procedure step(t:byte; ves:longint);var j: longint;begin j:= abs(obsh_ves - 2*ves); if j<min then min:= j; for j:= t+1 to n do step(j,ves+a[t]);end; begin assign(f,'in'); reset(f); n:=0; {кол-во всех предметов} obsh_ves:= 0; while not eof(f) do begin inc(n); read(f,a[n]); inc(obsh_ves,a[n]); end; close(f); min:= MaxLongInt; step(1,0); writeln('difference ',min)end.

Приведенная выше программа делает много лишней работы. Скажем, незачем продолжать генерирование очередного набора после того, как текущая разность уже превысила ранее найденный минимум. Кроме того, если в некоторый момент времени минимум вдруг окажется равным 1 или 0 (в зависимости от четности входных данных), то дальнейшие усилия также становятся ненужными, поскольку все равно ничего меньшего быть не может.

С учетом этих замечаний можно усовершенствовать текст программы. Мы оставляем эту несложную работу желающим.

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