Os algoritmos gananciosos (do inglês, greedy algorithms) são algoritmos que optam por uma escolha óptima localmente na esperança de encontrar uma solução óptima globalmente.
Esta técnica infelizmente nem sempre funciona para encontrar a solução óptima, mas quando funciona resulta num algoritmo bastante eficiente.
Vejamos um exemplo clássico dos greedy algorithms: encontrar o número mínimo de moedas que representem uma certa quantia.
Sejam as nossas moedas de Euro: 1, 2, 5, 10, 20, 50, 100 e 200 cêntimos. Qual é o menor número de moedas que somem, por exemplo, 16 cêntimos? Existem várias possibilidades. Posso usar só moedas de 1 (num total de 16 moedas), só moedas de 2 (8 moedas), posso escolher 10+5+1 cêntimos (3 moedas) que neste caso é a solução óptima.
A solução greedy para este problema passa por escolher, a cada momento, a moeda mais valiosa que ainda se pode usar. Se repetirmos este processo até que tenhamos o valor total, vamos obter a solução óptima.
Um exemplo de solução
public class Coins {
static int[] coins = {200, 100, 50, 20, 10, 5, 2, 1};
static int[] coinSolution(int amount) {
List<Integer> sol = new LinkedList<Integer>(); // list used to keep selected coins
int currentCoin = 0;
while (amount>0)
if (amount >= coins[currentCoin]) { // if we can still use current coin
amount -= coins[currentCoin];
sol.add(coins[currentCoin]);
} else
currentCoin++; // otherwise, go to the next smaller one
return sol.stream().mapToInt(i -> i).toArray(); // convert list to int[]
}
public static void main(String[] args) {
System.out.println(Arrays.toString(coinSolution(16)));
}
}
De reparar que as nossas moedas permitem usar a solução greedy, mas nem todos os conjuntos de moedas têm esta propriedade. Por exemplo, se as moedas fossem de 1, 3 e 4 cêntimos, e se quisermos obter a solução óptima para 6 cêntimos, a solução greedy não funciona (dar-nos-ia 4+1+1) para obter a solução óptima (que é 3+3).
Uma solução geral que possa ser usada para qualquer conjunto inicial de moedas tem de ser resolvida através de programação dinâmica.
Como exercício tentem resolver o UVa 11264 que é uma variante deste problema (se ficarem bloqueados, podem ler algumas pistas aqui).