MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-044

Enunciado: Para um conjunto finito de possíveis valores de moedas, deseja-se resolver o problema: "Encontrar o menor número de moedas para compor o troco de uma compra".  Uma abordagem plausível é utilizar o seguinte algoritmo guloso:

1. Escolhe-se a moeda de maior valor possivel que seja menor ou igual ao troco
2. Resolve-se o problema novamente descontando do troco inicial o valor da moeda escolhida no passo 1.

Qual dos conjuntos de valores de moedas faz com que o algoritmo acima retorne sempre uma solução ótima? Suponha que exista um estoque infinito de moedas de cada valor.

1. {1, 2, 10, 15, 30}
2. {1, 5, 10, 25, 50} 
3. {1, 2, 10, 25, 50}
4. O algoritmo guloso acima sempre retorna soluções ótimas
5. NDA

Ideia original de: Daniel Vidal