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

Вася часто участвует в благотворительных мероприятиях. То поможет деревья во дворе спасти от зайцев, то цветы в саду перед 1 сентября охраняет, то с бабушками на концерт Филиппа Киркорова сходит. Недавно он участвовал в спасении урожая одного фермера от кузнечиков. В благодарность фермер предложил Васе взять у него в магазине всё, что он хочет из того, что поместится к нему в рюкзак.
Да, задача не из легких. Конечно, Вася хочет взять самое ценное, что есть в магазине.
Но ему нужно помнить, что всё должно поместиться в рюкзак.
Какой алгоритм следует выбрать?
Например, можно придерживаться такой стратегии:
  1. Взять наиболее ценный предмет, который поместится в рюкзак.
  2. Выбрать следующий по стоимости товар с учётом того, что для него осталось место в рюкзаке.
И так до тех пор, пока остаются предметы в магазине и в рюкзаке есть место.
Но, к сожалению, такой алгоритм не всегда приведёт к правильному решению.
Рассмотрим пример:
Есть 3 предмета: чипсы, газировка и помидоры.
image
В рюкзак могут поместиться товары общим весом не более 1,6 кг.
В соответствии с алгоритмом выберем помидоры — они самые ценные и помещаются в рюкзак.
В этом случае больше ничего взять не получится.
А на самом деле, правильным вариантом было бы выбрать чипсы и газировку. Их общая стоимость больше стоимости помидоров и они вошли бы в рюкзак.
Этот пример показывает, что не каждая стратегия жадного алгоритма — верное решение задачи.
Но иногда не нужно подбирать идеальное решение, достаточно найти хорошее. Васе не так важно получить самые ценные предметы. В его случае жадный алгоритм вполне подойдёт.
Позже в курсе вы узнаете, как найти точное и при этом эффективное решение этой задачи.
Решите задачи D, E и F: https://contest.yandex.ru/contest/18360/enter/