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