O objetivo desse problema
é encontrar uma solução para o problema dado que minimize ou maximize o valor
de algum parâmetro. Os algoritmos que fazem o que parecem ser a “melhor”
escolha em cada passo são chamados de algoritmos vorazes. Para fazer isso, nós
demonstramos que a solução é ótima ou mostramos que há um contra-exemplo onde o
algoritmo produz uma solução que não é ótima.
Teorema 1: o algoritmo
voraz produz troncos usando o menos numero de moedas possíveis.
Exemplo 5:
Considera o problema
de fazer troncos com n centavos com moedas de 25, 10, 5 e 1 centavos e usar o
menos número de moedas. Em cada passo escolhemos a moeda com a maior
denominação possível para adicionar na pilha de troncos sem exceder n centavos.
Por exemplo, para organizar 67 centavos colocamos a moeda de 25 depois 25
novamente, depois 10, depois 5, depois 1, depois 1 novamente, totalizando 67
centavos.
Algoritmo Voraz