Algoritmos gulosos §

---

Um algoritmo guloso é uma estratégia de construção de algoritmos que toma decisões baseadas na melhor escolha disponível no momento, sem considerar as possíveis consequências futuras. A ideia é que, ao fazer uma série de escolhas localmente ótimas, o algoritmo chegue a uma solução globalmente ótima.

Abaixo um exemplo simples de um algoritmo guloso em C que resolve o problema da mochila fracionária (Fractional Knapsack Problem). Nesse problema, você tem uma mochila com uma capacidade limitada e um conjunto de itens, cada um com um peso e um valor. O objetivo é maximizar o valor total dos itens que podem ser colocados na mochila. Diferente do problema da mochila inteira, aqui você pode fracionar os itens.

#include <stdio.h>
 
// Estrutura para representar um item com peso e valor
typedef struct {
    int peso;
    int valor;
} Item;
 
// Função para comparar a razão valor/peso de dois itens
int comparar(const void *a, const void *b) {
    double r1 = (double)((Item *)a)->valor / ((Item *)a)->peso;
    double r2 = (double)((Item *)b)->valor / ((Item *)b)->peso;
    return r2 - r1 > 0 ? 1 : -1;
}
 
// Função para resolver o problema da mochila fracionária
double mochilaFracionaria(Item itens[], int n, int capacidade) {
    // Ordena os itens com base na razão valor/peso
    qsort(itens, n, sizeof(Item), comparar);
 
    double valorTotal = 0.0;
    int pesoAtual = 0;
 
    for (int i = 0; i < n; i++) {
        if (pesoAtual + itens[i].peso <= capacidade) {
            // Se o item cabe inteiro na mochila, adiciona-o
            pesoAtual += itens[i].peso;
            valorTotal += itens[i].valor;
        } else {
            // Se o item não cabe inteiro, adiciona a fração que cabe
            int pesoRestante = capacidade - pesoAtual;
            valorTotal += itens[i].valor * ((double)pesoRestante / itens[i].peso);
            break;  // A mochila está cheia
        }
    }
 
    return valorTotal;
}
 
int main() {
    int capacidade = 50;  // Capacidade da mochila
 
    // Array de itens {peso, valor}
    Item itens[] = {{10, 60}, {20, 100}, {30, 120}};
    int n = sizeof(itens) / sizeof(itens[0]);
 
    double maxValor = mochilaFracionaria(itens, n, capacidade);
    printf("Valor máximo que pode ser obtido = %.2f\n", maxValor);
 
    return 0;
}

Note

Neste exemplo, a estratégia gulosa é a escolha do item com a maior razão valor/peso em cada etapa. Essa abordagem pode não funcionar para todos os problemas de otimização, mas no caso da mochila fracionária, ela sempre resulta em uma solução ótima.

Referências §

---

https://drive.google.com/file/d/1vGZYPPw7PZuMMqXpjjUkF_kMGTmVv1-r/view?usp=drive_link