zxc17/backpack

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

Условие

Имеется рюкзак вместимостью N кг.

Имеется набор предметов, каждый из которых обладает весом и стоимостью.

Необходимо найти такую выборку предметов, которая помещается в рюкзак (суммарный вес не превышает вместимость) и имеет максимальную стоимость из всех возможных вариантов.

Каждый предмет можно положить в рюкзак один раз. Вес и стоимость - целые числа.

Пример

Рюкзак вместимостью 4 кг.

Предметы:

• магнитофон (вес=4, стоимость=3000)
• гитара (вес=1, стоимость=1500)
• ноутбук (вес=3, стоимость=2000)

Решение

Алгоритм решения взят из книги "Грокаем алгоритмы", автор Адитья Бхаргава.

Для решения необходимо создать множество рюкзаков с меньшей вместимостью. Поскольку по условию задачи у нас целые числа, и итоговый рюкзак вмещает 4 кг., то наше множество это 4 рюкзака с вместимостью 1,2,3,4. На старте каждый рюкзак пустой. В скобках указан набор предметов, после знака "=" общая стоимость выбранных предметов.

Рюкзак-1	Рюкзак-2	Рюкзак-3	Рюкзак-4
() = 0	() = 0	() = 0	() = 0

Внешний цикл: Перебираем предметы. Порядок перебора не имеет значения.

Внутреннй цикл: Для каждого рюкзака проверяем:

1. Помещается предмет в рюкзак? Если нет - содержимое рюкзака копируем из предыдущего шага итерации, переходим к следующему рюкзаку (пункты 2-3 пропускаем).
2. Если предмет помещается, то кладем его во временный список, вычисляем какой еще вес мы можем добавить в текущий рюкзак. Если значение больше нуля(обозначим его M), то во временный список добавляем список предметов из рюкзака-M предыдущего шага итерации.
3. Вычисляем стоимость предметов временного списка. Если она больше, чем на предыдущем шаге итерации, то заменяем содержимое рюкзака, иначе копируем старый набор.

По завершении обоих циклов в последнем рюкзаке будет оптимальный набор предметов

Рассмотрим на нашем примере

Исходные (пустые) наборы для каждого рюкзака:

Рюкзак-1	Рюкзак-2	Рюкзак-3	Рюкзак-4
() = 0	() = 0	() = 0	() = 0

Первый предмет - магнитофон (вес=4, стоимость=3000)

В первые три рюкзака он не помещается, копируем старые данные. Рюкзак-4 он заполняет полностью, его стоимость 3000, это больше предыдущего значения (0), значит обновляем данные.

Рюкзак-1	Рюкзак-2	Рюкзак-3	Рюкзак-4
() = 0	() = 0	() = 0	(м) = 3000

Второй предмет - гитара (вес=1, стоимость=1500).

В рюкзак-1 предмет помещается, заполняет полностью. Стоимость больше предыдущего значения(0), обновляем данные. В рюкзак-2 предмет помещается, можно дополнить еще на 1 кг. Смотрим рюкзак-1 из предыдущего шага - там пусто. Значит в нашем новом списке только текущий предмет. Его стоимость больше предыдущего значения(0), обновляем данные. Аналогично с третьим рюкзаком, обновляем данные. Рюкзак-4 - предмет помещается, можно добавить 3 кг. Рюкзак-3 с предыдущего шага итерации пустой, стоимость текущего предмета меньше, значит копируем старые данные.

Рюкзак-1	Рюкзак-2	Рюкзак-3	Рюкзак-4
(г) = 1500	(г) = 1500	(г) = 1500	(м) = 3000

Третий предмет - ноутбук (вес=3, стоимость=2000).

В первые два рюкзака не помещается, копируем старые данные. Рюкзак-3 - помещается, заполняет полностью, стоимость выше, обновляем данные. Рюкзак-4 - помещается, можно добавить еще 1кг. На предыдущем шаге итерации рюкзак-1 - это гитара стоимостью 1500. Суммарная стоимость нового списка - 3500. Это больше предыдущего значения (3000), обновляем данные.

Рюкзак-1	Рюкзак-2	Рюкзак-3	Рюкзак-4
(г) = 1500	(г) = 1500	(н) = 2000	(н, г) = 3500

Результат

В рюкзаке-4 находится искомый список. Ноутбук + гитара, общей стоимостью 3500.