28
What is an Algorithm Greedy ?
- What are its characteristics ?
- What are its advantages and disadvantages ?
28
What is an Algorithm Greedy ?
25
Algorithm Greedy is a common solution to optimization problems where:
Characteristics
Greedy Algorithms vs Dynamic Programming
Points in favor
Points Against
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;
}
}
Just to go deeper, the greedy change solution for this case is great. When two "consecutive coins" m[i]
and m_[i+1]
always satisfy 2*m_[i] <= m_[i+1]
then the greedy solution will always be great
Browser other questions tagged algorithm computer-science
You are not signed in. Login or sign up in order to post.
What is the reason for the negative?
– Ricardo
i reply: "Welcome to stackoverlow"
– Wallace Maxters
It wasn’t me. + 1, I also want to know what the greedy algorithm is.
– Wallace Maxters