Примечание. Графовая модель задачи (двудольный граф). Каждому жителю соответствует вершина в множестве X, каждой партии - вершина в множестве Y. Ребро (i,j) существует, если житель с номером i представляет партию с номером j. Требуется найти минимальное по мощности множество вершин S, такое, что SÍX и для любой вершины jÎY существует вершина iÎS, из которой выходит ребро в вершину j. Модификация задачи о нахождении минимального доминирующего множества.

5. Задача о рюкзаке (перебор вариантов)

Постановка задачи . В рюкзак загружаются предметы n различных типов (количество предметов каждого типа не ограничено). Максимальный вес рюкзака W. Каждый предмет типа i имеет вес w_i и стоимость v_i (i=1,2, ..., n). Требуется определить максимальную стоимость груза, вес которого не превышает W. Обозначим количество предметов типа i через k_i , тогда требуется максимизировать v₁ *k₁ +v₂ *k₂ +...+v_n *k_n при ограничениях w₁ *k₁ +w₂ *k₂ +...+w_n *k_n £W, где k_i - целые (0£k_i £[W/w_i ]), квадратные скобки означают целую часть числа.

Рассмотрим простой переборный вариант решения задачи, работоспособный только для небольших значений n (определить, для каких?). Итак, данные:

СonstMaxN=????;

Varn,w:integer;{количество предметов, максимальный вес}

Weight,Price:array[1..MaxN] of integer;{вес, стоимостьпредметов}

Best,Now:array[1..MaxN] of integer;{наилучшее, текущеерешения}

MaxPrice:LongInt;{наибольшая стоимость}

Решение, его основная часть - процедура перебора:

Procedure Rec(k,w:integer;st:LongInt);

{k - порядковый номер группы предметов, w - вес, который следует набрать из оставшихся предметов, st - стоимость текущего решения}

var i:integer;

begin

if (k>n) and (st>MaxPrice) then begin {найденорешение}

Best:=Now;MaxPrice:=st; end

else if k<=n then

for i:=0 to w div Weight[k] do begin

Now[k]:=i;

Rec(k+1,W-i*Weight[k],st+i*Price[k]);

end;

end;

Инициализация переменных, вывод решения и вызывающая часть (Rec(1,w,0)) очевидны. В данной логике отсутствуют блоки предварительной обработки, общих отсечений и отсечений по номеру предмета (смотрите задачу о парламенте). В блоке предварительной обработки целесообразно найти какое-то решение, лучше, если оно будет как можно ближе к оптимальному (наилучший вариант загрузки рюкзака). «Жадная» логика дает первое приближение. Кроме того, разумно выполнить сортировку, например, по значению стоимости предметов или отношению веса предмета к его стоимости. Построение блока общих отсечений аналогично тому, как это сделано в задаче о парламенте, а ответ на вопрос, почему предметы данного типа не стоит складывать в рюкзак, остается открытым.

Заключение

Инициализация переменных, вывод решения и вызывающая часть (Rec(1,w,0)) очевидны. В данной логике отсутствуют блоки предварительной обработки, общих отсечений и отсечений по номеру предмета (смотрите задачу о парламенте). В блоке предварительной обработки целесообразно найти какое-то решение, лучше, если оно будет как можно ближе к оптимальному (наилучший вариант загрузки рюкзака). «Жадная» логика дает первое приближение. Кроме того, разумно выполнить сортировку, например, по значению стоимости предметов или отношению веса предмета к его стоимости. Построение блока общих отсечений аналогично тому, как это сделано в задаче о парламенте, а ответ на вопрос, почему предметы данного типа не стоит складывать в рюкзак, остается открытым.

Литература

1. Ахо А.,Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов.-М.:Мир,1979.

2. Гэри М., Джонсон Д. Вычислительные алгоритмы и труднорешаемые задачи.-М.:Мир, 1982.

3. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы: Теория и практика.-М.:Мир,1980.

4. Суханов А.А. Олимпиадные задачи. Неопубликованный материал. - СПб.: 1996.