Questão 67317

Um professor de Algoritmos e Estruturas de Dados está ensinando sobre algoritmos gulosos (greedy algorithms). Ele quer que seus alunos compreendam a estratégia gulosa e, mais importante, que reconheçam que ela nem sempre leva à solução ótima global. Ele explica: "A estratégia gulosa constrói uma solução passo a passo, sempre fazendo a escolha que parece ser a melhor naquele momento (a 'escolha localmente ótima'). Para alguns problemas, como o problema de encontrar a árvore geradora mínima (com os algoritmos de Prim ou Kruskal), a estratégia gulosa de fato leva à solução globalmente ótima. Para outros, no entanto, ela pode levar a soluções sub-ótimas." Para ilustrar essa limitação, ele apresenta o clássico **Problema do Troco** (Change-Making Problem): dado um conjunto de moedas e um valor de troco, encontrar o menor número de moedas que somam esse valor. Ele mostra que, para o sistema de moedas brasileiro (1, 5, 10, 25, 50 centavos, 1 real), o algoritmo guloso (sempre pegar a maior moeda possível que não ultrapasse o valor restante) funciona perfeitamente. Em seguida, ele propõe um sistema de moedas hipotético, com os valores **{1, 7, 10}**, e pede aos alunos para darem o troco para o valor **15**.

Qual é o resultado do algoritmo guloso para dar o troco de 15 com as moedas {1, 7, 10}, e qual é a solução ótima? O que isso demonstra sobre a estratégia gulosa?