40
правок
Изменения
Заменены дефисы на тире.
{{Задача
|definition =
'''Задача о рюкзаке'''(''англ. Knapsack problem'') — дано <tex>N</tex> предметов, <tex>n_i</tex> предмет имеет массу <tex> w_i > 0</tex> и стоимость <tex> p_i > 0</tex>. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины <tex>W</tex> (вместимость рюкзака), а суммарная стоимость была максимальна.
}}
== Формулировка задачи ==
Дано <tex>N</tex> предметов, <tex>W</tex> - — вместимость рюкзака, <tex>w=\{w_{1},w_{2},...,w_{N}\}</tex> — соответствующий ему набор положительных целых весов, <tex>p=\{p_{1},p_{2},...,p_{N}\}</tex> — соответствующий ему набор положительных целых стоимостей. Нужно найти набор бинарных величин <tex>B=\{b_{1},b_{2},...,b_{N}\}</tex>, где <tex>b_{i} = 1 </tex>, если предмет <tex>n_i</tex> включен в набор, <tex> b_{i} = 0 </tex>, если предмет <tex>n_i</tex> не включен, и такой что:
#<tex>b_{1} w_{1}+ ... + b_{N} w_{N} \le W</tex>
#Если предмет <tex>k</tex> не попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимости рюкзака с такой же вместимостью и набором допустимых предметов <tex>\{n_1,n_2,...,n_{k-1}\}</tex>, то есть <tex>A(k,s) = A(k-1, s)</tex>
# Если <tex>k</tex> попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимости рюкзака, где вес <tex>s</tex> уменьшаем на вес <tex>k</tex> -ого предмета и набор допустимых предметов <tex>\{n_1,n_2,...,n_{k-1}\}</tex> плюс стоимость <tex>k</tex>, то есть <tex>A(k-1, s-w_k) + p_k</tex>
То есть:
=Другие задачи семейства=
==Ограниченный рюкзак ==
'''Ограниченный рюкзак''' (англ. ''Bounded Knapsack Problem'') - — обобщение классической задачи, когда любой предмет может быть взят некоторое количество раз.
'''Пример:''' Вор грабит склад. Он может унести ограниченный вес, каждый товар на складе содержится в определенном ограниченном количестве. Нужно унести предметов на максимальную сумму.
==Неограниченный рюкзак==
'''Неограниченный рюкзак''' (англ.''Unbounded Knapsack Problem'') - — обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.
'''Пример:''' Перекупщик закупается на оптовой базе. Он может увезти ограниченное количество товара, количество товара каждого типа на базе не ограниченно. Нужно увезти товар на максимальную сумму.
==Непрерывный рюкзак==
'''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') - — вариант задачи, в котором возможно брать любою дробную часть от предмета, при этом удельная стоимость сохраняется.
'''Пример:''' Вор грабит мясника. Суммарно он может унести ограниченный вес товаров. Вор может резать товары без ущерба к удельной стоимости. Нужно унести товара на максимальную сумму.
sort(); // сортируем в порядке убывания удельной стоимости.
for i = 1..N // идем по предметам
if W >= w[i] //если помещается - — берем
sum += p[i];
W -= w[i];
==Задача о суммах подмножеств==
'''Задача о суммах подмножеств''' (англ. ''Subset-sum Subset—sum problem, Value Independent Knapsack Problem'') - — задача из семейства, в которой стоимость предмета совпадает с его весом.
'''Пример:''' Машина может увезти определенное количество груза. Нужно увезти как можно больше крупного неделимого мусора за раз.
==Задача о размене==
'''Задача о размене''' (англ. ''Change-Making problem'') - — имеются <tex> N </tex> неисчерпаемых типов предметов с весами <tex>w_i</tex>. Нужно наполнить рюкзак предметами с суммарным весом <tex>W</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\le N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>. Задача: выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
'''Пример:''' У транспортной компании есть парк машин разной грузоподъемности. Нужно перевезти товара на максимальную сумму с одного склада на другой единовременно.
==Задача о назначении==
'''Задача о назначении''' (англ. ''Generalized Assignment Problem'') - — Наиболее общая задача семейства. Отличается от мультипликативного рюкзака тем, что каждый предмет имеет различные характеристики в зависимости от рюкзака, куда его помещают. Есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\le 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> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.
===Формулировка Задачи===
