Мне дано количество сказать $ 50. Мне даны некоторые деноминации: $ 1, $ 2, $ 5 и т. Д. И количество этих наименований, например 1, 5,6, что означает 1 монету/банкноту в размере 1, 5 монет/банкнот в размере 2 и 6 монет/банкнот в размере 5 долларов США. Мне нужно найти количество способов, которыми эти монеты можно использовать для формирования этой суммы 50 долларов США. Я пытаюсь найти эффективный алгоритм для решения этого в максимально сжатые сроки. Обратите внимание, что сумма не будет превышать 60 долларов США.Какой хороший алгоритм для решения этой алгоритмической головоломки?
Может кто-нибудь спросит, какой алгоритм я могу использовать для решения этой проблемы? До сих пор я написал рекурсивное решение этой проблемы, но для моей цели это слишком медленно. Я отправлю его здесь в ближайшее время.
Похоже, вы либо размещение домашних заданий или проблем здесь ... Если смотреть на другое место, как код игры в гольф (Http: //codegolf.stackexchange. com). Если ваша рекурация медленная, подумайте о «кэшированной рекурсии», которая будет хорошо работать в вашем случае (и имейте в виду, что вы можете сортировать сначала самые высокие счета. – Bruce
Посмотрите на проблему с рюкзаком. – RedX
@RedX: Да Я знаю проблему с рюкзаком но это для меньшего или равного веса/суммы. –