В лавке специи продаются на развес. У каждой специи есть доступный запас weight (граммы) и ценность этого запаса value. В сумку помещается capacity грамм. Специю можно взять целиком или частично — ценность пропорциональна весу. Допишите max_value(spices, capacity): функция возвращает максимальную суммарную ценность. Пропуски помечены # TODO.
Пример
spices = [("шафран", 10, 600), ("перец", 50, 500), ("корица", 40, 160)]
max_value(spices, 60) # 1100.0: весь шафран (600) + 50 г перца (500)
max_value(spices, 30) # 800.0: весь шафран + 20 г перца
Детали
- В главе 9 рюкзак, где предметы берутся только целиком, решается динамическим программированием. Здесь дробление разрешено — и жадный алгоритм даёт точный ответ.