Разбор задачи E. Печать

Тема: динамическое программирование
Сложность: выше среднего

Постановка задачи
Есть набор картриджей с параметрами: стоимость и количество страниц, которое может напечатать.
Найти минимальную сумму, которую нужно заплатить, чтобы мы могли распечатать ровно `k` страниц.

Решение
Нам имеет смысл рассматривать не более 200 картриджей
Картридж, у которого отношение стоимости к количеству напечатанных страниц максимально, имеет номер `"opt"`
Картридж с максимальным количеством страниц имеет номер `max`
Выгодно брать картридж `"opt"`, до тех пор когда количество страниц не станет меньше `p_max*p_"opt"`
А для количества страниц до `p_max*p_"opt"` решим стандартную задачу о рюкзаке

Обоснование
Имеет смысл считать только до `p_max*p_"opt"`, так как мы можем получить почти все остатки от деления на `p_"opt"`, не превышая `p_max*p_"opt"`. А, значит, этого хватает, чтобы понять, что алгоритм находит самое оптимальное решение.

Автор разбора: Аксёнов Виталий, СПбГУ ИТМО