Eu entendo como o algoritmo guloso para o problema de troca de moedas (pague uma quantia específica com o número mínimo possível de moedas) funciona - ele sempre seleciona a moeda com a maior denominação não excedendo a soma restante - e que sempre encontra a solução correta para conjuntos de moedas específicas.

Mas para alguns conjuntos de moedas, existem somas para as quais o algoritmo guloso falha. Por exemplo, para o conjunto{1, 15, 25} e a soma 30, o algoritmo guloso primeiro escolhe 25, deixando um resto de 5 e, em seguida, cinco 1s para um total de seis moedas. Mas a solução com o número mínimo de moedas é escolher 15 duas vezes.

Que condições um conjunto de moedas deve preencher para que o algoritmo guloso encontre a solução mínima para todas as somas?