Ready to put your newfound language skills into use? Get 40% off CodeCrafter's real-world proficiency projects!

Отримати знижку

Треки

Haskell

Вправи

Рюкзак

Середня

Вступ

Боб - крадій. Після місяців ретельного планування він нарешті зумів зламати системи безпеки розкішної крамниці.

Перед ним лежить багато предметів, і в кожного з них є своя цінність і вага. Боб охоче забрав би всі предмети, але його рюкзак витримує лише обмежену вагу. Тож Боб має ретельно обміркувати, які предмети взяти, щоб загальна цінність його вибору була якнайбільшою.

Вказівки

Мета - визначити, які предмети взяти, щоб загальна цінність вибору була максимальною, враховуючи вантажопідйомність рюкзака.

Предмети подаються як масив предметів. Кожен предмет має вагу і цінність. Усі наведені значення будуть строго додатними. Боб може взяти кожен предмет лише один раз.

Наприклад:

Items: [
  { "weight": 5, "value": 10 },
  { "weight": 4, "value": 40 },
  { "weight": 6, "value": 30 },
  { "weight": 4, "value": 50 }
]

Knapsack Maximum Weight: 10

Для наведеного вище прикладу перший предмет має вагу 5 і цінність 10, другий предмет має вагу 4 і цінність 40, і так далі. У цьому прикладі Боб має взяти другий і четвертий предмети, щоб максимізувати цінність, яка в цьому випадку становить 90. Він не може отримати більше ніж 90, бо рюкзак має обмеження ваги 10.