Я не определял здесь L, так как это было по сути дела продолжение предыдущих комментов из этого треда, где было сказано следующее:
> L -- максимальное достоинство монеты
То есть в итоге алгоритм выглядит следующим образом. Полагаем a[i]=0 и рассматриваем цикл по i от 1 до 2L-1. Для данного i рассматриваем монету максимального достоинства k не превосходящего i, полагая затем a[i]=1+a[i-k]. После прохождения цикла в a[i] хранится число шагов "жадного" алгоритма, нужное для того, чтобы набрать сумму i.
Теперь проходим цикл по i заново, где при каждом i первое слагаемое варьируем, то есть внутри цикла возникает ещё один. Переменная j нового цикла пробегает все возможные достоинства монет, меньшие i. При этом смотрим на величину 1+a[i-j] и проверяем, не будет ли она при каком-то j меньше нежели a[i].
Тут в целом можно добавить кое-какие ограничения, но на порядок числа выполняемых операций это, видимо, не влияет.
Что касается минимальности числа проверок, то я над этим пока не думал. Я пока не знаю, совпадает ли описанное с тем, что Вы предлагаете.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
циклы
Date: 2007-07-08 03:35 pm (UTC)> L -- максимальное достоинство монеты
То есть в итоге алгоритм выглядит следующим образом. Полагаем a[i]=0 и рассматриваем цикл по i от 1 до 2L-1. Для данного i рассматриваем монету максимального достоинства k не превосходящего i, полагая затем a[i]=1+a[i-k]. После прохождения цикла в a[i] хранится число шагов "жадного" алгоритма, нужное для того, чтобы набрать сумму i.
Теперь проходим цикл по i заново, где при каждом i первое слагаемое варьируем, то есть внутри цикла возникает ещё один. Переменная j нового цикла пробегает все возможные достоинства монет, меньшие i. При этом смотрим на величину 1+a[i-j] и проверяем, не будет ли она при каком-то j меньше нежели a[i].
Тут в целом можно добавить кое-какие ограничения, но на порядок числа выполняемых операций это, видимо, не влияет.
Что касается минимальности числа проверок, то я над этим пока не думал. Я пока не знаю, совпадает ли описанное с тем, что Вы предлагаете.