Допустим есть безграничное кол-во купюр, номиналами a, b и c
Как определить максимальное количество купюр сумма которых будет равна N ?
Была идея находить минимальный номинал, потом находить такое максимальное k при котором k*min <= N, а потом циклом отнимать 1 от k и подставлять другие номиналы, пока это все не будет == N
Но естественно это срабатывает далеко не всегда, и слишком долго работает на больших числах
Какой алгоритм действий ко всему этому можно придумать?
p.s. решение задачи должно быть без использования рекурсии и функций
-
почитайте про Задачу о ранце и ее вариации– teran25 фев 2018 в 16:43
-
Задача о рюкзаке– Anton Shchyrov25 фев 2018 в 16:44
1 ответ
Ну, по логике (принимая a < b < c
) запишем функцию count(N)
так:
Если N==0
- возвращаем 0.
Если N < a
- сообщаем об ошибке.
Если N
делится на a
- то функция возвращает N/a
.
Если нет - то ищем максимум count(N-b)
и count(N-c)
, и возвращаем его + 1.
Смотрим, и если работает медленно - привязываем к этому мемоизацию.
Ищем, само собой, count(N)
...
"По-моему, так" (с) Пух
-
К сожалению в условии решения задачи нельзя использовать циклы, но все равно благодарю за вариант 25 фев 2018 в 18:33
-
@Bogdan Bida: Это где такое сказано в условии задачи? Перечитал пять раз - в упор не вижу. При этом вы сами там говорите: "циклом отнимать". 25 фев 2018 в 18:35
-
Мой косяк, забыл упомянуть (думал решение сразу делается одной формулой или парой циклов) 25 фев 2018 в 18:37
-
Ну тогда просто разверните динамическое программирование в обратную сторону и стройте тот же массив значений в обратном порядке...– Harry25 фев 2018 в 19:28