Эпилог

Достаточно классическая задача, похожая на задачу о рюкзаке. Основное отличие — предметов мало, но вместо этого для каждого предмета есть большое количество возможных замен.

Решение при этом тоже не сильно отличается от решения задаче о рюкзаке: заведем динамику  — минимальный «штраф» за то, чтобы набрать суммарную площадь w с помощью первых i фото. Порядок пересчета динамики будет сначала по увеличению i, а затем по увеличению w. Останется только для каждого фото перебрать bi и сделать обновление

Общее время работы решения — .