Имеется рюкзак вместимостью N кг.
Имеется набор предметов, каждый из которых обладает весом и стоимостью.
Необходимо найти такую выборку предметов, которая помещается в рюкзак (суммарный вес не превышает вместимость) и имеет максимальную стоимость из всех возможных вариантов.
Каждый предмет можно положить в рюкзак один раз. Вес и стоимость - целые числа.
Рюкзак вместимостью 4 кг.
Предметы:
- магнитофон (вес=4, стоимость=3000)
- гитара (вес=1, стоимость=1500)
- ноутбук (вес=3, стоимость=2000)
Алгоритм решения взят из книги "Грокаем алгоритмы", автор Адитья Бхаргава.
Для решения необходимо создать множество рюкзаков с меньшей вместимостью. Поскольку по условию задачи у нас целые числа, и итоговый рюкзак вмещает 4 кг., то наше множество это 4 рюкзака с вместимостью 1,2,3,4. На старте каждый рюкзак пустой. В скобках указан набор предметов, после знака "=" общая стоимость выбранных предметов.
Рюкзак-1 | Рюкзак-2 | Рюкзак-3 | Рюкзак-4 |
---|---|---|---|
() = 0 | () = 0 | () = 0 | () = 0 |
Внешний цикл: Перебираем предметы. Порядок перебора не имеет значения.
Внутреннй цикл: Для каждого рюкзака проверяем:
- Помещается предмет в рюкзак? Если нет - содержимое рюкзака копируем из предыдущего шага итерации, переходим к следующему рюкзаку (пункты 2-3 пропускаем).
- Если предмет помещается, то кладем его во временный список, вычисляем какой еще вес мы можем добавить в текущий рюкзак. Если значение больше нуля(обозначим его M), то во временный список добавляем список предметов из рюкзака-M предыдущего шага итерации.
- Вычисляем стоимость предметов временного списка. Если она больше, чем на предыдущем шаге итерации, то заменяем содержимое рюкзака, иначе копируем старый набор.
По завершении обоих циклов в последнем рюкзаке будет оптимальный набор предметов
Рассмотрим на нашем примере
Исходные (пустые) наборы для каждого рюкзака:
Рюкзак-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.