Published

14/04/2026

Modified

01/04/2026

Algoritmos Gulosos

1. O Que São Algoritmos Gulosos?

Algoritmos gulosos (greedy algorithms) são heurísticas muito utilizadas na solução de problemas combinatórios e de otimização. Nesses problemas, existe um vasto espaço de busca recheado de combinações possíveis (soluções viáveis e inviáveis), e o nosso objetivo é encontrar uma solução viável que maximize ou minimize uma certa função objetivo.

A principal característica de um algoritmo guloso é simples, mas poderosa: a cada decisão, ele sempre faz a escolha que parece mais promissora naquele exato instante, sem pensar no futuro ou reconsiderar o passado.

“Come e nunca vomita.”
— Analogia humorística das aulas sobre algoritmos gulosos.

Como em um jogo de Pac-Man engolindo a pastilha mais próxima sem prever os movimentos dos fantasmas a longo prazo, o algoritmo faz escolhas míopes (locais).

Propriedades Fundamentais

Um algoritmo guloso constrói uma solução etapa por etapa baseado em duas premissas vitais:

Escolha localmente ótima: Uma vez tomada a decisão de incluir ou descartar um candidato, essa decisão nunca é revista. Não há backtracking (volta atrás). Ele é rápido porque nunca se arrepende.
Subestrutura Ótima: A solução ótima global para o problema costuma ser formada pela combinação de escolhas locais também ótimas.

O Funcionamento Lógico

Normalmente, todo algoritmo guloso baseia-se em cinco componentes lógicos: * Conjunto de Candidatos: As opções disponíveis na entrada. * Função de Seleção: O critério guloso que aponta qual é o melhor candidato restante. * Função de Viabilidade: Garante que adicionar aquele candidato à nossa resposta não viola as regras do problema. * Função de Solução: Verifica se o conjunto de elementos já construído satisfaz a demanda total e resolveu o problema. * Função Objetivo: Aquilo que queremos maximizar (ex: lucro) ou minimizar (ex: custo, distância).

[!TIP] O Grande Segredo dos Gulosos: A chave para um algoritmo guloso funcionar rápido e bem está em ordenar corretamente os dados de entrada. A ordenação cria o critério pelo qual o algoritmo vai “devorar” as opções de forma ótima, garantindo resoluções eficientes, frequentemente em $O(N \log N)$.

2. Exemplo Prático: Abastecimento Estratégico (Postos de Gasolina)

Imagine o seguinte problema: você é dono de uma rede de postos de gasolina. O setor de pesquisa lhe envia uma lista com preços e estoques dos seus maiores fornecedores. A demanda necessária do mercado é $d$ litros em $n$ fornecedores possíveis. Cada fornecedor possui um estoque $e_i$ de litros de gasolina, vendidos ao preço $p_i$ por litro. Qual a estratégia para gastar o mínimo possível comprando a demanda $d$?

A Ideia Gulosa

Qual é a primeira ideia? Ordenar os fornecedores pelos preços, do mais barato para o mais caro. Com a lista ordenada, iniciamos nosso algoritmo guloso: tentamos comprar o máximo possível do fornecedor mais barato disponível. Quando seu estoque acaba, ou se já compramos tudo dele, passamos para o próximo mais barato, até obtermos a demanda.

A lógica funciona perfeitamente: se sobrasse gasolina em um fornecedor $A$ (mais barato) e tivéssemos comprado de um $B$ (mais caro), seria um erro. Escolhendo os mais baratos sempre, garantimos o menor custo.

A ordenação custa $O(n \log n)$ e percorrer o vetor depois para fazer a compra (“ser guloso”) custa $O(n)$. O algoritmo como um todo roda confiantemente na complexidade assintótica $O(n \log n)$.

Abaixo, a implementação completa do pensamento nas três principais linguagens competitivas:

C++

#include <iostream>
#include <algorithm>
#include <iomanip>
#define MAXN 100100
using namespace std;

struct gas {
  double preco, estoq;
};

// Critério Guloso: A função que compara para ordenar pelo Menor Preço
bool compara(gas x, gas y) { 
  return x.preco < y.preco;
}

gas forn[MAXN];
int n;
double d, custo;

int main() {
  cin >> n >> d;
  for(int i = 1; i <= n; i++) {
    cin >> forn[i].preco >> forn[i].estoq;
  }
  
  // Ordenar as opções (O Segredo!)
  sort(forn + 1, forn + n + 1, compara);
  
  // Percorro o vetor devorando (sendo guloso) as opções viáveis
  for(int i = 1; i <= n; i++) {
    gas davez = forn[i];
    
    // Se o fornecedor tem menos gasolina do que eu ainda preciso
    if(davez.estoq < d) {
      custo += davez.estoq * davez.preco; 
      d -= davez.estoq; 
    }
    // Caso contrário (ele tem o suficiente para zerar minha demanda)
    else {
      custo += d * davez.preco; 
      d = 0; 
      break; 
    }
  }
  
  if(d) cout << "Impossivel\n"; // Se ao fim do vetor ainda falta demanda
  else  cout << fixed << setprecision(2) << custo << "\n";
  
  return 0;
}

Java

import java.util.*;

class Fornecedor {
    double preco;
    double estoq;
}

public class PostosGasolina {
    public static void main(String[] args) {
        Locale.setDefault(Locale.US);
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        double d = sc.nextDouble();
        Fornecedor[] forn = new Fornecedor[n];

        for (int i = 0; i < n; i++) {
            forn[i] = new Fornecedor();
            forn[i].preco = sc.nextDouble();
            forn[i].estoq = sc.nextDouble();
        }

        // Ordenando através do comparador customizado: do mais barato ao mais caro
        Arrays.sort(forn, Comparator.comparingDouble(f -> f.preco));

        double custo = 0.0;
        for (int i = 0; i < n && d > 0; i++) {
            Fornecedor f = forn[i];
            if (f.estoq < d) {
                custo += f.estoq * f.preco;
                d -= f.estoq;
            } else {
                custo += d * f.preco;
                d = 0; // Saciei minha demanda
            }
        }

        if (d > 0) System.out.println("Impossivel");
        else       System.out.printf(Locale.US, "%.2f%n", custo);
    }
}

Python

def main():
    n_d = input().split()
    n = int(n_d[0])
    d = float(n_d[1])

    fornecedores = []
    for _ in range(n):
        preco_str, estoq_str = input().split()
        preco = float(preco_str)
        estoq = float(estoq_str)
        fornecedores.append((preco, estoq))

    # O método sort e função lambda apontando a ordenação pelo preço
    fornecedores.sort(key=lambda x: x[0])

    custo = 0.0
    for preco, estoq in fornecedores:
        if d <= 0:
            break
        if estoq < d:
            custo += estoq * preco
            d -= estoq
        else:
            custo += d * preco
            d = 0

    if d > 0:
        print("Impossivel")
    else:
        print(f"{custo:.2f}")

if __name__ == "__main__":
    main()

3. Seleção de Atividades (O Problema do Dentista)

Um dos problemas clássicos onde algoritmos gulosos brilham é em gerenciar o acoplamento de atividades conflitantes. Imagine que você dispõe de várias atividades agendadas querendo usar um mesmo recurso exclusivo (uma sala de aula, uma linha de produção, ou uma cadeira de dentista!). Cada atividade possui horário de início e horário de término. Mas duas atividades não podem ocorrer ao mesmo tempo.

O objetivo? Maximizar o número total de atividades atendidas.

O famoso problema OBI “Dentista” (2010), ilustra que sua heurística nem sempre é óbvia de cara. O dentista precisa atender a maior quantidade possível de pacientes ao longo do dia, não havendo prioridade médica, apenas numérica.

Vamos explorar três tentativas gulosas – três formas diferentes de tentar ordenar as consultas:

Tentativa 1: Escolher as consultas que COMEÇAM primeiro

Parece natural. A cada instante, checar quem chega primeiro no consultório e atender até esgotar o tempo. - Exemplo de falha: - Consulta $A$: inicia 08h e vai até 18h. - Consulta $B$, $C$ e $D$: iniciam 09h, 11h, 15h, durando apenas 1 hora cada. Se escolhermos quem começa primeiro, pegamos $A$, e seremos incapazes de atender $B, C, D$. Atendemos 1 pessoa em vez de 3. A função heurística falhou.

Tentativa 2: Escolher as consultas com MENOR DURAÇÃO

E se pegarmos sempre o paciente mais rápido? Isso salvaria a tentativa anterior. Vejamos se a heurística funciona sempre. - Exemplo de falha: - Paciente 1: das 09h às 12h. (Duração: 3 horas) - Paciente 2: das 11h às 13h. (Duração: 2 horas) - Paciente 3: das 12h às 15h. (Duração: 3 horas) Com a métrica de “menor duração”, atendemos primeiro o paciente 2 (11h às 13h). Como os pacientes 1 e 3 entram em conflito de horário com o paciente 2, atendemos no total apenas 1 paciente. Contudo, caso priorizássemos as consultas, poderíamos ter atendido os pacientes 1 e 3. A heurística falhou novamente.

Tentativa 3: Escolher as consultas que TERMINAM primeiro (A Estratégia de Ouro!)

Imagine a cena prática: Você acabou de atender e vai à recepção chamar o próximo. Várias pessoas poderiam entrar no momento, qual você pega? A lógica dita: A que vai sair mais rápido da cadeira, te entregando o seu equipamento novamente para a próxima consulta! Assim, fazemos a ordenação lógica por fim da consulta. O dentista sempre atende a próxima consulta que não conflita com a última encerrada e que termina o mais cedo possível. Esse critério garante matematicamente o máximo de inserções não sobrepostas.

Implementação do clássico C++ com essa ordenação:

#include <iostream>
#include <algorithm>
#define MAXN 10100
using namespace std;

struct compromisso {
  int ini, fim;
}; 

// A GRANDE DIFERENÇA: Critério de ordenar pelo TÉRMINO mais rápido
bool compara(compromisso a, compromisso b){
  return a.fim < b.fim;
}

compromisso consulta[MAXN]; 
int n, livre, qtd; 

int main(){
  cin >> n; 
  for(int i = 1; i <= n; i++){
    cin >> consulta[i].ini >> consulta[i].fim;
  }
  
  // Ordena os compromissos com base do seu horário de fim
  sort(consulta + 1, consulta + n + 1, compara);
  
  // Como as consultas estão ordenadas de modo ótimo, varremos com O(N)
  for(int i = 1; i <= n; i++){ 
    if(consulta[i].ini >= livre){ 
      qtd++; // Atende o paciente
      livre = consulta[i].fim; // Agora estarei enrolado com isso até esta hora
    }
  }
  
  cout << qtd << "\n"; 
  return 0;
}

Abaixo o equivalente núcleo dessa heurística na linguagem adaptada, em Java, se fosse gerenciar uma “Seleção de Eventos”:

public class SelecaoDeAtividadesGuloso {
    static int selecaoGulosa(int[] ini, int[] fim, int n){
        int ultimaSelecionada = 0;
        int selecionadas = 0;

        if (n == 0) return 0;

        // A primeira atividade, ordenadas pelo fim, é sempre selecionada.
        System.out.print("a" + 0 + " ");
        selecionadas++;

        for (int i = 1; i < n; i++) {
            // Se o início da próxima atividade testada é sucessivo ao encerramento da última
            if (ini[i] >= fim[ultimaSelecionada]) {
                System.out.print("a" + i + " ");
                selecionadas++;
                ultimaSelecionada = i;
            }
        }
        System.out.println();
        return selecionadas;
    }
}

4. Limitações: Quando Gulosos Erram? (O Problema da Mochila)

Algoritmos gulosos são rápidos e simples de implementar. Mas: nem sempre encontram a solução global ótima! A prova definitiva disso é o Problema da Mochila (Knapsack Problem).

O Problema: Dispomos de uma mochila com capacidade de peso máxima $(W)$. Temos um conjunto de itens, em que cada item possui um peso e um valor. Como montar a mochila de tal forma que o valor total carregado seja máximo, sem estourar o limite de peso?

A abordagem gulosa clássica consistiria em criar um critério matemático: avaliamos a métrica de “Densidade de Lucro” calculando a razão valor / peso. Depois ordenamos os itens de forma decrescente por essa densidade, alocando os mais valiosos para o seu peso primeiramente.

4.1. Mochila Fracionária: Sucesso Total

Na Mochila Fracionária (ex: ouro em pó, areia de prata), os itens podem dividir suas frações. - Você aplica a ordenação pela razão de valor/peso. - Enche a mochila com o item de maior métrica. Quando o peso chegar no limite, você fraciona o pó final, pegando os $K$ quilos restantes para tapar a boca da mochila. - Resultado: Solução Gulosa garante otimalidade e gera a solução verdadeira!

4.2. Mochila 0-1 (Binária): Falha Catastrófica!

Na variação 0-1, as escolhas são binárias: você leva todo o item, ou deixa todo o item. Você não fraciona. Tratam-se de produtos consolidados (um carro de mão, um fogão, uma estátua).

Exemplo Prático: Mochila capacidade $= 50$. - Objeto 1: Peso 10, Valor 60 ($Raz\tilde{a}o = 6$) - Objeto 2: Peso 20, Valor 100 ($Raz\tilde{a}o = 5$) - Objeto 3: Peso 30, Valor 120 ($Raz\tilde{a}o = 4$)

Pelo algoritmo Fracionário (Guloso): Pega-se Objeto 1 e 2 integralmente ($Peso = 30$, falta 20). Pegaria 2/3 do Objeto 3, e teria seu ótimo global de $240$. Mas estamos lidando com objetos inteiros e indestrutíveis neste problema.

Pelo algoritmo Guloso no problema 0-1: 1. Escolhe Objeto 1 (o melhor!). Sobram 40 na mochila. 2. Escolhe Objeto 2 (o outro melhor!). Sobram 20 na mochila. 3. Objeto 3 testado. Pesa 30 e os 20 de espaço o barram de entrar. Descartado. Total Valor do Guloso: 160.

No entanto, o Ótimo Global Real seria: Não levar o Objeto 1, para permitir que sobrem os $50$ da mochila integralmente para despachar o Objeto 2 (20kg) e o Objeto 3 (30kg). Total Valor Real: Objeto 2 + Objeto 3 = 220!

[!CAUTION] A estratégia da busca Gulosa encontrou a solução míope (160) bloqueada pelos seus primeiros movimentos, deixando os valiosos $220 reais para o esquecimento. Para resolver problemas como a Mochila 0-1, descarta-se a estratégia gulosa e utiliza-se a técnica de Programação Dinâmica.

5. Exemplo Prático: Intercalação Ótima de Vetores

O custo computacional afeta muito as operações básicas da programação. Imagine que você precisa intercalar/fundir inúmeros vetores (Listas) ordenados para mesclar arquivos em uma única super lista, à moda algorítmica de um Merge. Quando você faz uma fusão (merge) de um vetor (tamanho $A$) com outro vetor (tamanho $B$), o número somado de comparações será $(|A| + |B| - 1)$.

O grande problema surge quando você tem múltiplos vetores (ex: tamanhos $V_1=15$, $V_2=10$ e $V_3=5$). A ordem em que você os intercala importa muito e altera o tempo das repetições computacionais! * Opção 1: $V_1+V_2$ e depois somar com $V_3$. (Fará 53 comparações). * Opção 2: $V_2+V_3$ e depois somar com $V_1$. (Fará 43 comparações). * Opção 3: $V_1+V_3$ e depois somar com $V_2$. (Fará 48 comparações).

O Critério Guloso Multi-Merge

Para processar esses vetores eficientemente e gerar os menores arranjos para a fila total, propõe-se um algoritmo Guloso ótimo: Sempre extraia (Merge) os dois menores vetores disponíveis do lote de opções no seu turno. Ao fundi-los, reinsira na lista o “vetor pai” que foi criado.

Se temos as pilhas de tamanho estipulado em [10, 20, 30, 40, 50], a estratégia correta operaria assim: 1. Menores pilhas: 10 e 20. Fundo em 30. Conjunto passa a ser [30, 30, 40, 50]. 2. Menores pilhas: 30 e 30. Fundo em 60. Conjunto passa a ser [40, 50, 60]. 3. Menores: 40 e 50. Fundo em 90. Conjunto: [60, 90]. 4. Finaliza: Fundo os 150.

Esse fluxo empilhando constantemente as menores instâncias gera algo similar à uma árvore de Huffman, minimizando bruscamente o número de operações lógicas alocadas na memória. É uma das grandes vitórias da Estratégia Gulosa aplicadas na gerência de arrays.

6. Sumário e Aplicações Clássicas

O paradigma dos Algoritmos Gulosos é como encarnar o papel de um rápido detetive perante o problema, mais do que ser um matemático explorador. Eles geram escolhas rápidas de aproximações nos espaços complexos e que funcionam perfeitamente naquelas situações onde subestruturas lineares definem o máximo do todo!

Vantagens dos Gulosos	Desvantagens dos Gulosos
Alta simplicidade e didática na formulação computacional e lógica.	Funcionalidade pode depender violentamente da escolha do critério guloso aplicado.
São os mais rápidos perante vastos lotes de dados ($O(N\log N)$).	Frequentemente perdem em problemas complexos não garantindo a ótima Global.
Código super reduzido, que foca na Ordenação e frequentemente em um loop linear (for).	Não é robusto a arcos reversos. Nunca altera o estado no passado por não possuir backtracking.

Aplicações Famosas baseadas integralmente em metodologias gulosas que dominam os gráficos e problemas reais: - Algoritmo de Dijkstra: Descobrimento de caminhos mínimos partindo da raiz em Grafos. - Árvores Geradoras Mínimas (Spanning Trees): Feitas primorosamente pelos algoritmos gulosos de Prim e de Kruskal. - Cobertura de Conjuntos Algorítmica (Set Cover): Abordagens clássicas do critério da cobertura total em menor custo (Chvátal). - Códigos de Compressão Ótima: Extração e representação por Huffman.

Exercícios Sugeridos

Resolva os problemas “Dentista” ou “Telemarketing” passados para exercitar a ordenação e a correta aplicação das heurísticas de busca restrita por prioridades.
Modele em uma folha de papel, e depois codificando, se a solução do “Problema do Troco” brasileiro comum (oferecer o mínimo de moedas possíveis a um cliente) funciona sob um Algoritmo Guloso (com moedas de $R\$0.50$, $R\$0.25$, $R\$0.10$ e $R\$0.05$). Em seguida, teste com uma moeda customizada incluída: E se criarmos a moeda de $R\$0.40$ para testar a heurística novamente sobre dar $R\$0.80$ de troco? (Dica: Você notará uma belíssima falha do guloso em situações de “sistemas não-canônicos”).