Изменения

* Методом [[Meet-in-the-middle|Meet-in-the-middle]]. Сложность решения <tex> O({2^{N/2}}*{N}) </tex>

* Метод динамического программирования. Сложность — <tex>O(N*WNW)</tex>.

Пусть <tex>A(k, s)</tex> есть максимальная стоимости стоимость предметов, которые можно уложить в рюкзак вместимости <tex>s</tex>, если можно использовать только первые <tex>k</tex> предметов, то есть <tex>\{n_1,n_2,\dots,n_k\}</tex>, назовем этот набор допустимых предметов для <tex>A(k,s)</tex>.

Метод динамического программирование всё равно не повзволяет позволяет решать задачу за полиномиальное время, потому что задача о ранце (или задача о рюкзаке) — одна из [[Класс NP|NP-полных]] задач комбинаторной оптимизации.

'''for''' i = 0 '''to W''' w

'''for''' i = 0 '''to N''' n A[i][0] = 0 ''<font color="green">// Первые элементы приравниваем к 0</font>'' '''for''' k = 1 '''to N ''' n '''for''' s = 1 '''to W ''' w ''<font color="green">//Перебираем для каждого k все вместимости</font>'' '''if''' s >= w[k] ''<font color="green">//Если текущий предмет вмещается в рюкзак</font>'' A[k][s] = max(A[k-1][s], A[k-1][s-w[k]]+p[k]) ''<font color="green">//выбираем Выбираем класть его или нет</font>''

A[k][s] = A[k-1][s] ''<font color="green">//иначеИначе, не кладем</font>''

'''function''' findAns('''int''' k, '''int''' s)

'''if''' A[k-1][s] == A[k][s] findAns(k-1, s)

findAns(k-1, s - w[k])

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

Начиная с <tex>A(5, 13)</tex> восстанавливаем ответ. Будем идти в обратном порядке по <tex>k</tex>. ''<font color="red000000">Красным обозначен фоном обозначим наш путь</font>''

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

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

'''for''' i = 0 '''to W ''' w ''<font color="green">// базаБаза</font>''

'''for''' i = 1 '''to N ''' n '''for''' c = 1 '''to W ''' w ''<font color="green">//Перебираем для каждого i, все вместимости </font>''

'''for''' l = min(b[i], c / w[i]) to '''downto''' 1 ''<font color="green">//ищем Ищем l для которого выполняется максимум </font>''

Сложность алгоритма <tex>O(N*WNW^2)</tex>. 

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

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

sort() ''<font color="green">// сортируем Сортируем в порядке убывания удельной стоимости.</font>''  '''for''' i = 1 '''to N ''' n ''<font color="green">// идем Идем по предметам </font>'' '''if''' W w > w[i] ''<font color="green">//если Если помещается — берем</font>'' sum += p[i] W w -= w[i] '''else''' sum += W w / w[i] * p[i] ''<font color="green">// иначе Иначе берем сколько можно и выходим</font>'' '''break'''

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

'''Задача об упаковке''' (англ. ''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> \sum_{i=1}^M x_{ij} \leq leqslant 1 \qquad j=1, \ldots, N</tex>.