Изменения

Перейти к: навигация, поиск

Задача о рюкзаке

362 байта добавлено, 03:11, 5 июня 2017
Нет описания правки
=Другие задачи семейства=
==Ограниченный рюкзак==
{{Задача
|definition =
}}
=== Пример ===
Вор грабит склад. Он может унести ограниченный вес, каждый товар на складе содержится в определенном ограниченном количестве. Нужно унести предметов на максимальную сумму.
Сложность алгоритма <tex>O(NW^2)</tex>.
==Неограниченный рюкзак==
{{Задача
|definition =
}}
===Пример===
Перекупщик закупается на оптовой базе. Он может увезти ограниченное количество товара, количество товара каждого типа на базе не ограниченно. Нужно увезти товар на максимальную сумму.
Сложность алгоритма <tex>O(NW)</tex>.
==Непрерывный рюкзак==
{{Задача
|definition =
}}
===Пример===
Вор грабит мясника. Суммарно он может унести ограниченный вес товаров. Вор может резать товары без ущерба к удельной стоимости. Нужно унести товара на максимальную сумму.
'''break'''
==Задача о суммах подмножеств==
{{Задача
|definition =
}}
===Пример===
Машина может увезти определенное количество груза. Нужно увезти как можно больше крупного неделимого мусора за раз.
Сложность алгоритма <tex>O(NW)</tex>.
==Задача о размене==
{{Задача
|definition =
Сложность алгоритма <tex>O(NW)</tex>.
==Задача об упаковке==
{{Задача
|definition =
}}
===Пример===
Нужно вывезти из шахты все куски руды, используя наименьшее число вагонеток.
Применение динамического программирования нецелесообразно. Обычно применяют аппроксимационные алгоритмы, либо используют метод ветвей и границ.
==Мультипликативный рюкзак==
{{Задача
|definition =
}}
===Пример===
У транспортной компании есть парк машин разной грузоподъемности. Нужно перевезти товара на максимальную сумму с одного склада на другой единовременно.
Применение динамического программирования, для задач данного типа нецелесообразно. Используются вариации метода ветвей и границ.
==Задача о назначении==
{{Задача
|definition =
}}
===Пример===
Выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
40
правок

Навигация