Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 23
Вы бы хоть написали в начале поста что за задачу решаете-то… Ну хотя бы чтобы слова про "знаменитой задаче с монетами, которыми необходимо отсчитать сдачу" были ссылкой на соответствующую статью в википедии.
Знаменитая задача с монетами, это когда надо за несколько взвешиваний определить фальшивую.
Советская система 1,2,3,5 — не каноническая?
А система 1, 30, 100 — каноническая или нет? Попробуйте разменять 120.
Пойду поищу точное определение канонической системы.
Будете удивлены. Каноническая монетная система — это такая, для которой жадный алгоритм дает оптимальное решение задачи размена для любого целого числа.
Обычная динамика по таблице даёт O(kn), не нужно мемоизации, где k — число номиналов, n — сумма
Мемоизация — меморизация наверное?)
Нет.
вторая – это количество разрядов числа, представляющего сдачу.
обычный инт64 и цена мл. разряда = минимальной монете и никаких проблем.
Это, в каком то смысле, переоткрытие приближенного решения задаче о рюкзаке с помощью динамического программирования.
Под С я понимаю сумму. Т.е. сложность, как вы справедливо заметили выше: «Сложность Вашего алгоритма — как минимум Ω(n^2). Самый худший для Вас вариант — это когда все номиналы — простые числа. » Только «как максимум»
И да, это вариация динамического программирования. Если для каждой точки запоминать результат, решение будет оптимальным.
И да, это вариация динамического программирования. Если для каждой точки запоминать результат, решение будет оптимальным.
А тесты будут?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Задача о сумме