Изменения

* Перебирать все подмножества набора из N предметов. Сложность такого решения <tex>O({2^{N}})</tex>.

== Метод динамического программирования ==

ans.push(k)

== Пример ==

=Другие задачи семейства=

'''Ограниченный рюкзак''' (англ. ''Bounded Knapsack Problem'') — обобщение классической задачи, когда любой предмет может быть взят некоторое количество раз.

Вор грабит склад. Он может унести ограниченный вес, каждый товар на складе содержится в определенном ограниченном количестве. Нужно унести предметов на максимальную сумму.

===Формулировка Задачи===

d[i][c] = max(d[i][c], d[i - 1][c - l * w[i]] + p[i] * l)

'''Неограниченный рюкзак''' (англ.''Unbounded Knapsack Problem'') — обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.

Перекупщик закупается на оптовой базе. Он может увезти ограниченное количество товара, количество товара каждого типа на базе не ограниченно. Нужно увезти товар на максимальную сумму.

===Формулировка Задачи===

Сложность алгоритма <tex>O(NW)</tex>.

'''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') — вариант задачи, в котором возможно брать любою дробную часть от предмета, при этом удельная стоимость сохраняется.

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

===Формулировка Задачи===

'''break'''

'''Задача о суммах подмножеств''' (англ. ''Subset—sum problem, Value Independent Knapsack Problem'') — задача из семейства, в которой стоимость предмета совпадает с его весом.

Машина может увезти определенное количество груза. Нужно увезти как можно больше крупного неделимого мусора за раз.

===Формулировка Задачи===

Сложность алгоритма <tex>O(NW)</tex>.

{{Задача

|definition =

Сложность алгоритма <tex>O(NW)</tex>.

'''Задача об упаковке''' (англ. ''Bin Packing Problem'') — имеются <tex> N </tex> рюкзаков вместимости <tex> W </tex> и столько же предметов с весами <tex>w_i</tex>. Нужно распределить все предметы, задействовав минимальное количество рюкзаков.

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

===Формулировка Задачи===

Применение динамического программирования нецелесообразно. Обычно применяют аппроксимационные алгоритмы, либо используют метод ветвей и границ.

'''Мультипликативный рюкзак''' (англ. ''Multiple Knapsack Problem'') — есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\leqslant N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>. Задача: выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.

У транспортной компании есть парк машин разной грузоподъемности. Нужно перевезти товара на максимальную сумму с одного склада на другой единовременно.

===Формулировка Задачи===

Применение динамического программирования, для задач данного типа нецелесообразно. Используются вариации метода ветвей и границ.

'''Задача о назначении''' (англ. ''Generalized Assignment Problem'') — Наиболее общая задача семейства. Отличается от мультипликативного рюкзака тем, что каждый предмет имеет различные характеристики в зависимости от рюкзака, куда его помещают. Есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\leqslant N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>, у <tex> j </tex> предмета <tex> p_{ij} </tex> стоимость и вес, при помещении его в <tex> i </tex> рюкзак, равны <tex> p_{ij} </tex> и <tex> w_{ij} </tex> соответственно.

Выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.

Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.

===Формулировка Задачи===