What’s a greedy algorithm?

Question

What is an Algorithm Greedy ?

• What are its characteristics ?
• What are its advantages and disadvantages ?

Answer 1

Algorithm Greedy is a common solution to optimization problems where:

• Makes the choice that seems to be best at the moment in the hope that it entails in a solution or prevention of future problems to global level.
• It is simple and easy to implement;
• He is short-sighted: he makes decisions based on the information available on current iteration.

Characteristics

• Never regret a decision, the choices made are definitive;
• It does not take into account the consequences of its decisions;
• You can do repetitive calculations;
• It does not always produce the best solution (it depends on the amount of information provided);
• The more information, the greater the chance to produce a better solution.

Greedy Algorithms vs Dynamic Programming

• In a dynamic programming algorithm the choice may depend on the solution of the subproblems, while a greedy algorithm will try to choose the best solution at that time.
• The solution of problems in dynamic programming from the bottom up, while a greedy algorithm goes from top to bottom, i.e., in programming dynamics, the solutions for all subproblems are calculated from the smaller subproblems for larger.
• The results of subproblems in dynamic programming are saved, facilitating proof of correction.

Points in favor

• Simple and easy to implement;
• Algorithms for fast execution;
• Can provide the best solution (ideal state).

Points Against

• Information-dependent;
• They run the risk of going into endless loops;
• Situational, only solve specific types of problems;
• Decisions taken shall be irrevocable;

Sample code (in this case a simple implementation of a greedy change return)

import java.text.DecimalFormat;

public class Troco {

    public String calculaTroco(double conta, double pago) {
        DecimalFormat formatador = new DecimalFormat("###,##0.00");
        if (pago < conta)
            return ("\nPagamento insuficiente, faltam R$" + formatador.format(conta - pago) + "\n");
        else {

            String resultado;
            double troco;

            troco = pago - conta;
            resultado = "\nTroco = R$" + formatador.format(troco) + "\n\n";

            resultado = this.calculaNotas(troco, resultado);
            resultado = this.calculaMoedas(troco, resultado);

            resultado = resultado + "\n";

            return (resultado);
        }
    }

    private String calculaNotas(final double troco, String resultado) {

        int nota[] = { 100, 50, 20, 10, 5, 2, 1 };

        int valor;
        int ct;

        int contadorNota = 0;

        valor = (int) troco;
        while (valor != 0) {
            ct = valor / nota[contadorNota]; // calculando a qtde de notas
            if (ct != 0) {
                resultado = resultado + (ct + " nota(s) de R$" + nota[contadorNota] + "\n");
                valor = valor % nota[contadorNota]; // sobra
            }
            contadorNota++; // próxima nota
        }
        return resultado;
    }

    private String calculaMoedas(final double troco, String resultado) {

        int centavos[] = { 50, 25, 10, 5, 1 };

        int contadorMoeda = 0;
        int valor;
        int ct;

        valor = (int) Math.round((troco - (int) troco) * 100);
        while (valor != 0) {
            ct = valor / centavos[contadorMoeda]; // calculando a qtde de moedas
            if (ct != 0) {
                resultado = resultado + (ct + " moeda(s) de" + centavos[contadorMoeda] + "centavo(s)\n");
                valor = valor % centavos[contadorMoeda]; // sobra
            }
            contadorMoeda++; // próximo centavo
        }
        return resultado;
    }

}