Алгоритмы работы с множествами

B_m1,B_m-11…, B₁1.

3. Поместить последовательность  из пункта 2 за последовательностью из пункта 1.

Пример для n=3.

Коду Грея порядка n=1 соответствует два одноразрядных вектора:

0,1.

Поместим 0 после каждого, получили

00,10.

Реверсируем последовательность 0,1 и  дописываем им 1, получаем:

11,01.

 Объединяем – получаем:

00,10,11,01.

Это найдены B_i для n=2.

Теперь опять дописываем к ним 0, реверсируем  и к ним 1, а потом  все объединяем и получаем в итого:

000, 100, 110, 010, 011, 111, 101, 001.

Нерекурсивная версия построения кода Грея приведена в алгоритме 3.

Алгоритм 3. Нерекурсивное построение кода Грея.

1. В качестве начального взять  вектор B=(0,…,0), т.е. для каждого i=1,…,n B[i]=0.

2. Присвоить i=0, где i- число построенных двоичных векторов.

3. Вывести текущее значение вектора  B.

3. Увеличить i на 1, т.е. i=i+1;

4. Найти p как наибольшую степень двойки, которая делит нацело i.

5. Если p<n, то B[p+1]=1-B[p+1], и вернуться к пункту 3. Иначе остановка.

Реализовать решение следующей  задачи.

Задача о  рюкзаке

Задача о рюкзаке — одна из задач линейной комбинаторной оптимизации. Подобные задачи часто возникают в экономике, прикладной математике, криптографии.

Сформулируем задачу в общем случае.

Дано k предметов, i-й предмет имеет массу w_i > 0 и стоимость p_i > 0. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины W (вместимость рюкзака – в некоторой определенной величине), а суммарная стоимость была максимальна. Другими словами, нужно определить набор бинарных величин (b₁, b₂,..., b_k), такой, что

b₁w₁ + b₂w₂ +...+ b_kw_k

W,

а величина b₁p₁ + b₂p₂ +...+ b_kp_k -- максимальная. Величина b_i равна 1, если i-й предмет включается в набор, и равна 0 в противном случае.

Задача укладки рюкзака очень сложна. Если перебирать всевозможные подмножества данного набора из k предметов, то получится решение сложности не менее чем O(2^k). В настоящее время неизвестен (и, скорее всего, вообще не существует) алгоритм решения этой задачи, сложность которого является многочленом от k.

Мы рассмотрим решение данной задачи для случая, когда все входные  данные -- целочисленные, сложность алгоритма будет O(kW).

Решение

Задача о рюкзаке в случае, когда вес каждого предмета представляет собой целое число, может быть решена с помощью обычно линейного перебора всех подмножеств или с помощью динамического программирования. Стоит отметить, что данная задача  является NP-задачей (псевдо-полиномиальна).

Требуется решить задачу с помощью  одного из перечисленных выше алгоритма  перебора подмножеств множества.

В качестве проверочного примера можно использовать такой рюкзак:

Пусть максимальная вместимость рюкзака W = 15, количество предметов k = 5, их стоимости и массы таковы:  
w₁ = 6, p₁ = 5,    w₂ = 4, p₂ = 3,    w₃ = 3, p₃ = 1,  
w₄ = 2, p₄ = 3,    w₅ = 5, p₅ = 6.

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