dav

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Para um conjunto finito de possiveis valores de moedas, deseja-se resolver o problema: "Encontrar o menor numero de moedas para compor o troco de uma compra"

Utiliza-se  um algoritmo guloso que segue os passos:

1. Escolhe-se a moeda de maior valor possivel  que seja menor do que o 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 leve a soluções ótimas?

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

Ideia original de: Daniel Vidal