Algoritmos gulosos constituem uma poderosa ferramenta para a solução de problemas em um tempo computacionalmente viável. No entanto, dependendo das...

Algoritmos gulosos constituem uma poderosa ferramenta para a solução de problemas em um tempo computacionalmente viável. No entanto, dependendo das características do problema, algumas estratégias gulosas não são capazes de alcançar soluções ótimas. Um exemplo é o problema de devolver o valor (troco) com o uso da menor quantidade de moedas possível. Considerando o algoritmo guloso apresentado para esse problema, analise as afirmativas a seguir. I. A execução do algoritmo com os parâmetros (c1 = 20, c2 = 15, c3 = 23, c4 = 41) e n = 22 produz uma solução ótima. II. Para n = 38 e 48 (c1 = 25, c2 = 10, c3 = 23, c4 = 5), nenhuma moeda c4 comporá a solução final. III. A complexidade O(n) do algoritmo constitui o melhor caso possível para esse problema. IV. O algoritmo guloso apresentado é capaz de encontrar a solução ótima para qualquer conjunto de moedas. Agora, assinale a alternativa que apresenta a sequência correta.

I. A execução do algoritmo com os parâmetros (c1 = 20, c2 = 15, c3 = 23, c4 = 41) e n = 22 produz uma solução ótima.
II. Para n = 38 e 48 (c1 = 25, c2 = 10, c3 = 23, c4 = 5), nenhuma moeda c4 comporá a solução final.
III. A complexidade O(n) do algoritmo constitui o melhor caso possível para esse problema.
IV. O algoritmo guloso apresentado é capaz de encontrar a solução ótima para qualquer conjunto de moedas.
a) V, F, F, F
b) F, V, F, F
c) F, F, V, F
d) F, F, F, V
e) F, V, V, F