Условие
Турист уже уложил в рюкзак всё необходимое и может взять с собой дополнительные вещи общей массой не более 8 кг. Каждую вещь можно взять не больше одного раза. Вещь | Масса | Полезность (в баллах) Мангал | 4 кг | 9 Гамак | 3 кг | 7 Бадминтон | 1 кг | 2 Фонарь | 1 кг | 3 Настольные игры | 3 кг | 6 Какую наибольшую суммарную полезность может набрать турист?
Подсказка
Перебирайте наборы, к которым нельзя добавить ни одной вещи без превышения массы.
Для каждого набора посчитайте массу и сумму баллов.
Показать ответ
19
Пошаговое решение
- Понимаем ограничение
Все вещи вместе весят 12 кг — больше 8 кг, значит, от чего-то придётся отказаться. Ищем набор массой не более 8 кг с наибольшей суммой баллов.
- Перебираем наборы, в которые уже ничего не добавить
Если в набор помещается ещё вещь, её выгодно добавить (баллы только растут). Поэтому достаточно проверить наборы, к которым ничего нельзя добавить без перегруза: Мангал + Гамак + Фонарь: 8 кг, 19 баллов Мангал + Гамак + Бадминтон: 8 кг, 18 баллов Мангал + Фонарь + Настольные игры: 8 кг, 18 баллов Гамак + Бадминтон + Фонарь + Настольные игры: 8 кг, 18 баллов Мангал + Бадминтон + Настольные игры: 8 кг, 17 баллов Мангал + Бадминтон + Фонарь: 6 кг, 14 баллов
- Выбираем лучший набор
Наибольшая полезность 19 баллов: Мангал + Гамак + Фонарь, масса 8 кг. Здесь и выбор вещей по убыванию баллов даёт тот же набор, но убедиться, что лучше набрать нельзя, позволяет только перебор.
Ответ: 19