Данная задача решается методом динамического программирования. Пусть c[k] – минимальная сумма денег, необходимая для покупки k пар носок. Предположим, что для заданного k нам уже известны все значения c[i] для i = 1 .. k-1. Исходя из данного предположения, определим значение c[k]. Очевидно, что для покупки k носков необходимо будет воспользоваться услугами одного из поставщиков. Поэтому рассмотрим каждого поставщика в отдельности, предполагая его вхождение в число используемых поставщиков. Допуская вхождение i-го поставщика в список используемых мы можем определить, что c[k] = c[k-a[i]]+b[i], если a[i]
Умея вычислять c[k] по предыдущим значениям, мы можем перебрать все значения k от 1 до n и вычислить c[n] – ответ на задачу. Таким образом, сложность задачи составляет O(m∙n)), что согласно ограничениям задачи позволяет уложиться в установленные временные рамки. Данный алгоритм решения может быть представлен следующим образом:
read(n, m);
for i=1..m read(a[i], b[i])
for k=1..n{
c[k]=inf
for i=1..m
if(a[i] < k) c[k] = min(c[k], b[i]+c[k-a[i]])
else c[k] = min(c[k], b[i])
}
write(c[n])
