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