Определите оптимальную комбинацию монет на сумму в долларах

Question

Мне нужно найти наиболее оптимальную комбинацию монет, которая составляет определенную сумму в долларах. По сути, я хочу использовать наименьшее количество монет, чтобы добраться туда.

Например:

если в валютной системе есть монеты: {13, 8, 1}, жадное решение изменит значение 24 на {13, 8, 1, 1, 1}, но истинное оптимальное решение - {8, 8 , 8}.

Я хочу написать это в Javascript, но псевдокод - это хорошо, так как я уверен, что это поможет большему количеству людей.

Answer 1

В общем, проблема фактически является NP-полной (см. Проблема изменения ).Однако для многих валютных систем (включая систему США {1, 5, 10, 25}) жадный алгоритм также оказывается оптимальным.

Answer 2

Эта проблема кричит Динамическое программирование .

Базовый псевдокод должен выглядеть примерно так:

• Пусть C (n) - минимальное количество монет, используемых для суммирования до n .
• На каждом рекурсивном шаге найдите следующую монету максимального значения, c , и выберите C (n) :
• минимальное значение между C (nc) + 1 (с использованием указанной монеты, обновлением общего количества использованных монет и оставшимся значением) и C (n) (без использования монета) - в обоих случаях удаление c из списка доступных монет для следующей итерации.

Обратите внимание, что этот алгоритм будет полезен для общего случая, на который вы ссылаетесь. Для любой другой системы монет, в которой каждая монета является делителем на одну после нее (большинство систем монет в мире), жадное решение является самым простым и оптимальным.