84
правки
Изменения
Нет описания правки
=== Реализация ===
<font color=darkgreen>// sum - — массив сумм a + b, cnt - — счетчик массива sum</font>
'''function''' findsum('''int[]''' A):
'''for''' a = 0..N - 1
Реализуем данный алгоритм:
<font color=darkgreen>// N - — количество всех вещей, w[] - — массив весов всех вещей, cost[] - — массив стоимостей всех вещей, R - — ограничение по весу рюкзака.</font>
'''function''' knapsack(): '''int'''
sn = N / 2
Дан граф <tex>G</tex>, в котором <tex>N</tex> вершин. Требуется подсчитать количество полных подграфов графа <tex>G</tex> (такие подграфы также называются '''кликами''' (англ. ''clique'')).
Наивное решение - — перебор всех возможных подграфов и проверка для каждого, что он является кликой, сложность - — <tex>O(2^N \times N^2)</tex>
Этот алгоритм можно улучшить до <tex>O(2^N \times N)</tex>. Для этого нужно в функции перебора хранить маску вершин, которые мы ещё можем добавить. Поддерживая эту маску, можно добавлять только «нужные» вершины, и тогда не нужно будет в конце проверять подграф на то что он — клика. Добавлять вершину можно за <tex>O(1)</tex>, используя побитовое «и» текущей маски и строчки матрицы смежности добавляемой вершины.
Для одной клики <tex>K</tex> графа <tex>{G}_1</tex> может быть несколько подходящих клик в <tex>{G}_2</tex>. О клике <tex>K</tex> мы "знаем" только маску вершин графа <tex>{G}_2</tex>, которые ещё можно добавить. Для каждой такой маски в <tex>{G}_2</tex> нужно предподсчитать ответ.
С помощью динамического программирования предподсчитаем для каждой маски вершин графа <tex>{G}_2</tex> количество клик, вершины которых являются подмножеством выбранной маски. Количество состояний - — <tex>2^{N/2}</tex>. Количество переходов:<tex>N</tex> . Асимптотика - — <tex>O(2^{N/2} \times N)</tex>.
Для каждой клики <tex>K</tex> (в том числе и пустой) графа <tex>{G}_1</tex> прибавим к глобальному ответу предподсчитанное количество клик, которые можно добавить к <tex>K</tex> (В том числе и пустых). Асимптотика: <tex>O(2^{N/2})</tex>.
