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

Но для некоторых наборов монет существуют суммы, для которых жадный алгоритм не работает. Например, для набора{1, 15, 25} и сумма 30, жадный алгоритм сначала выбирает 25, оставляя остаток 5, а затем пять 1, в общей сложности шесть монет. Но решение с минимальным количеством монет состоит в том, чтобы выбрать 15 дважды.

Каким условиям должен соответствовать набор монет, чтобы жадный алгоритм нашел минимальное решение для всех сумм?