Propriedades Fundamentais

Algoritmos gananciosos são aplicáveis apenas a problemas que demonstram duas características críticas. A propriedade de escolha gananciosa exige que decisões localmente ótimas conduzam inevitavelmente à solução global ótima. Paralelamente, a estrutura ótima de subproblemas implica que a solução ótima do problema original contenha soluções ótimas para seus subproblemas derivados.

Mecanismo Operacional

Diferente da programação dinâmica, que integra soluções de subproblemas anteriores, a abordagem gananciosa toma decisões imediatas baseadas apenas no estado atual. Este método reduz progressivamente o escopo do problema sem revisitar escolhas passadas, visando alcançar a otimização global através de sucessivas otimizações locais. Ambos os paradigmas dependem da estrutura ótima de subproblemas, mas divergem na forma de exploração do espaço de soluções.

Estratégia de Implementação

A resolução de problemas por algoritmos gananciosos envolve três fases essenciais. Primeiro, a análise do problema define estados, objetivos de otimização e restrições. Segundo, a formulação da estratégia gananciosa deetrmina como cada decisão local reduzirá o problema. Terceiro, a validação matemática comprova que a estratégia satisfaz as propriedades fundamentais, frequentemente utilizando indução ou prova por contradição. A fase crítica reside na concepção da estratégia, que pode variar desde soluções intuitivas até abordagenns não óbvias que exigem experiência algorítmica.

Exemplos Práticos

Minimização de Moedas no Troco

Para calcular o menor número de moedas (valores 1, 5, 10, 20, 50) necessárias para dar troco de valor T, seleciona-se iterativamente a maior denominação possível até zerar o valor restente.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    const vector<int> valores = {50, 20, 10, 5, 1};
    int valor_compra;
    cin >> valor_compra;
    int restante = 100 - valor_compra;
    int quantidade = 0;
    
    for (int moeda : valores) {
        quantidade += restante / moeda;
        restante %= moeda;
    }
    cout << quantidade << endl;
    return 0;
}

Cobertura Mínima de Segmentos

Dado um segmento [S, T] e N intervalos, busca-se cobrir totalmente [S, T] com o menor número de intervalos. A solução ordena os intervalos pelo ponto inicial e seleciona iterativamente o intervalo que mais se estende à direita a partir da posição atual.

#include <iostream>
#include <algorithm>
using namespace std;

struct Intervalo {
    int inicio, fim;
};

int main() {
    int s, t, n;
    cin >> s >> t >> n;
    vector<Intervalo> intervalos(n);
    
    for (int i = 0; i < n; i++) 
        cin >> intervalos[i].inicio >> intervalos[i].fim;
    
    sort(intervalos.begin(), intervalos.end(), 
        [](const Intervalo& a, const Intervalo& b) {
            return a.inicio < b.inicio;
        });
    
    int cobertura_atual = s;
    int indice = 0;
    int total_intervalos = 0;
    bool completo = false;

    while (cobertura_atual < t && indice < n) {
        int max_fim = cobertura_atual;
        // Encontra intervalo com maior extensão à direita
        while (indice < n && intervalos[indice].inicio <= cobertura_atual) {
            if (intervalos[indice].fim > max_fim) 
                max_fim = intervalos[indice].fim;
            indice++;
        }
        if (max_fim == cobertura_atual) break;
        
        total_intervalos++;
        cobertura_atual = max_fim;
        if (cobertura_atual >= t) {
            completo = true;
            break;
        }
    }
    cout << (completo ? total_intervalos : -1) << endl;
    return 0;
}

Localização Ótima de Centro de Distribuição

Para minimizar a distância total entre um depósito e N lojas posicionadas em uma reta, a mediana das coordenadas das lojas fornece a solução ótima. Este resultado explora a propriedade matemática de que a mediana minimiza a soma das distâncias absolutas.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int quantidade_lojas;
    cin >> quantidade_lojas;
    vector<int> posicoes(quantidade_lojas);
    
    for (int i = 0; i < quantidade_lojas; i++)
        cin >> posicoes[i];
    
    sort(posicoes.begin(), posicoes.end());
    int mediana = posicoes[quantidade_lojas / 2];
    long long distancia_total = 0;
    
    for (int pos : posicoes)
        distancia_total += abs(pos - mediana);
    
    cout << distancia_total << endl;
    return 0;
}