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