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

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

Рассмотрим эвристический (жадный) алгоритм решения задачи о рюкзаке.

Пример.

Грузоподъемность 9
Веса 6, 5, 4
Стоимости 24, 19, 14
24/6 > 19/5 > 14/4

Согласно алгоритму в рюкзак нужно положить предмет в весом 6. Однако очевидно, что в этом случае нужно положить в рюкзак предметы с весами 5 и 4.