Problema da mochila fracionada: algoritmo ganancioso com exemplo

O que é estratégia gananciosa?

Algoritmos gananciosos Em cada etapa, escolhe-se a melhor opção local na esperança de que uma cadeia de ótimos locais produza uma solução globalmente ótima. Assim como a Programação Dinâmica, esses métodos visam problemas de otimização, mas nunca revisitam decisões anteriores.

Os algoritmos gulosos geralmente são simples de escrever, rápidos (frequentemente em tempo linear ou quadrático), fáceis de depurar e consomem pouca memória. A desvantagem é que o resultado nem sempre é o ideal, portanto, a estratégia só funciona para problemas que possuem uma estrutura comprovadamente segura contra algoritmos gulosos.

As estratégias gulosas resolvem problemas de otimização combinatória construindo uma solução A, um componente Ai, de cada vez. A cada passo, você escolhe Ai de forma ótima, considerando as restrições atuais, e reduz o problema a um subproblema menor.

Para que um método guloso seja considerado correto, duas propriedades devem ser satisfeitas:

1. Propriedade de escolha gananciosa: Um ótimo local em cada etapa leva a um ótimo global. A escolha depende de decisões passadas, mas não de decisões futuras.
2. Subestrutura ideal: A solução ótima do problema como um todo contém as soluções ótimas de seus subproblemas.

Um algoritmo ganancioso tem cinco componentes:

1. Um conjunto de candidatos a partir do qual as soluções são construídas.
2. Uma função de seleção que escolhe o melhor candidato seguinte.
3. Uma função de viabilidade que verifica se um candidato pode estender a solução parcial atual.
4. Uma função objetivo que avalia uma solução completa ou parcial.
5. Uma função de avaliação que sinaliza quando a solução está completa.

A ideia do ganancioso

O Greedy One classifica os pacotes apenas pelo valor:

• Ordene os pacotes em ordem decrescente de valor.
• Percorra a lista ordenada e adicione cada pacote à mochila, caso haja espaço suficiente para acomodá-lo.

Essa regra nem sempre fornece a resposta ideal. Contraexemplo:

• Parâmetros: n = 3, M = 19.
• Pacotes: {i = 1; W = 14; V = 20}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 8} — alto valor, mas também alto peso.
• O jogador ganancioso escolhe o pacote 1 com valor total de 20, enquanto a escolha ideal (pacote 2, pacote 3) chega a 24.

A ideia dos dois gananciosos

A Greedy Two classifica os pacotes apenas pelo peso:

• Ordene os pacotes em ordem não decrescente de peso.
• Percorra a lista ordenada e adicione cada pacote à mochila, caso haja espaço suficiente para acomodá-lo.

Essa regra também não é ideal. Contraexemplo:

• Parâmetros: n = 3, M = 11.
• Pacotes: {i = 1; W = 5; V = 10}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 28} — peso leve, mas baixo valor.
• Ganancioso: Duas opções (pacote 1, pacote 2) com valor total de 26, enquanto a escolha ótima (pacote 3) atinge 28.

A ideia dos três gananciosos

O algoritmo Greedy Three corrige ambas as falhas combinando valor e peso em uma única chave de classificação. É o método padrão para o Problema da Mochila Fracionária.

• Calcule o custo unitário V[i] / W[i] para cada pacote.
• Ordene os pacotes em ordem decrescente de custo unitário.
• Percorra a lista ordenada e adicione cada pacote se houver espaço disponível para ele.

Classificação gananciosa de três ordens por custo unitário V[i] / W[i]

Idéia: Calcule a relação valor-peso V[i] / W[i] para cada pacote, ordene em ordem decrescente e pegue primeiro a maior relação disponível até que a mochila esteja cheia.

Para o verdadeiro fracionário Na variante, quando o próximo pacote não couber inteiro, pegue uma fração que preencha exatamente a capacidade restante. Essa regra extra é o que torna o Greedy Three comprovadamente ótimo no Fractional Knapsack.

Etapas do Algoritmo

Para a variante branch-and-bound 0/1, a lista de custos unitários ordenada direciona uma árvore de busca:

• Passo 1: O nó raiz representa uma mochila vazia. ValorTotal = 0. LimiteSuperior = M × custo unitário máximo.
• Passo 2: Crie ramificações na raiz de acordo com a quantidade de cópias do pacote de maior proporção que podem ser acomodadas. Para cada ramificação filha, recalcule TotalValue, a capacidade restante M e UpperBound.
• Passo 3: Expanda primeiro a criança com o maior limite superior, na esperança de encontrar rapidamente uma solução eficaz.
• Passo 4: Elimine qualquer nó cujo limite superior não seja melhor do que a melhor solução completa atual.
• Passo 5: Quando cada nó é expandido ou podado, a melhor solução completa atual é considerada ótima.

Pseudocódigo para o algoritmo guloso da Mochila Fracionária pura:

Fractional Knapsack (Array W, Array V, int M)
1. for i <- 1 to size(V)
2.     cost[i] <- V[i] / W[i]
3. Sort-Descending(cost)
4. total <- 0
5. i <- 1
6. while (i <= size(V) and M > 0)
7.     if W[i] <= M
8.         M <- M - W[i]
9.         total <- total + V[i]
10.        i <- i + 1
11.    else
12.        total <- total + V[i] * (M / W[i])
13.        M <- 0

Complexidade do algoritmo:

• Usando uma ordenação simples (seleção ou bolha): O(n²).
• Usando o quicksort ou o merge sort: O(n log n), dominado pela etapa de ordenação.

Java Code para os Três Gananciosos

Definir o KnapsackPackage Classe com peso, valor e custo derivado (a relação V/W usada para a classificação):

public class KnapsackPackage {

    private double weight;
    private double value;
    private Double cost;

    public KnapsackPackage(double weight, double value) {
        super();
        this.weight = weight;
        this.value = value;
        this.cost = Double.valueOf(value / weight);
    }

    public double getWeight() { return weight; }

    public double getValue() { return value; }

    public Double getCost()  { return cost; }
}

Em seguida, crie a função que implementa o algoritmo Greedy Three:

public void knapsackGreProc(int W[], int V[], int M, int n) {
    KnapsackPackage[] packs = new KnapsackPackage[n];
    for (int i = 0; i < n; i++) {
        packs[i] = new KnapsackPackage(W[i], V[i]);
    }

    Arrays.sort(packs, new Comparator<KnapsackPackage>() {
        @Override
        public int compare(KnapsackPackage a, KnapsackPackage b) {
            return b.getCost().compareTo(a.getCost());
        }
    });

    double remain = M;
    double result = 0d;

    for (int i = 0; i < n && remain > 0; i++) {
        if (packs[i].getWeight() <= remain) {
            remain -= packs[i].getWeight();
            result += packs[i].getValue();
            System.out.println("Pack " + i + " - Weight " + packs[i].getWeight()
                             + " - Value " + packs[i].getValue());
        } else {
            double fraction = remain / packs[i].getWeight();
            result += packs[i].getValue() * fraction;
            System.out.println("Pack " + i + " - Fraction " + fraction
                             + " - Value " + packs[i].getValue() * fraction);
            remain = 0;
        }
    }

    System.out.println("Max Value:\t" + result);
}

Função mochilaGreProc() em Java

Explicação do código:

1. Envolva cada entrada em um KnapsackPackage Assim, a chave de classificação (relação V/W) é pré-calculada.
2. Ordene por ordem decrescente de custo.
3. Se cada pacote couber, leve-o inteiro.
4. Utilize uma fração da próxima embalagem para preencher o espaço restante.
5. Pare assim que a capacidade restante chegar a zero.

Nota de correção: o original Java loop avançado i somente quando um pacote não cabia, o que fazia com que o mesmo pacote fosse retirado repetidamente. A versão acima avança um pacote por iteração e adiciona uma etapa de preenchimento fracionário, correspondendo à verdadeira regra da Mochila Fracionária.

Java Driver que executa o algoritmo em um exemplo prático:

public void run() {
    int W[] = new int[]{15, 10, 2, 4};
    int V[] = new int[]{30, 25, 2, 6};
    int M = 37;
    int n = V.length;
    knapsackGreProc(W, V, M, n);
}

Python3 Code para os Três Gananciosos

Primeiro defina o KnapsackPackage aula. O __lt__ O método permite a ordenação direta por custo:

class KnapsackPackage(object):
    """Knapsack Package Data Class"""

    def __init__(self, weight, value):
        self.weight = weight
        self.value  = value
        self.cost   = value / weight

    def __lt__(self, other):
        return self.cost < other.cost

Em seguida, implemente a rotina da Mochila Fracionária:

class FractionalKnapsack(object):

    def knapsackGreProc(self, W, V, M, n):
        packs = [KnapsackPackage(W[i], V[i]) for i in range(n)]
        packs.sort(reverse=True)

        remain = M
        result = 0

        for i in range(n):
            if remain == 0:
                break
            if packs[i].weight <= remain:
                remain -= packs[i].weight
                result += packs[i].value
                print("Pack", i, "- Weight", packs[i].weight, "- Value", packs[i].value)
            else:
                fraction = remain / packs[i].weight
                result += packs[i].value * fraction
                print("Pack", i, "- Fraction", fraction,
                      "- Value", packs[i].value * fraction)
                remain = 0

        print("Max Value:", result)

Função mochilaGreProc() em Python

Nota de correção: o original Python classe definida como vazia __init__ sem corpo, o que levanta IndentationErrorA versão acima remove o construtor vazio porque nenhum é necessário.

Driver que executa o algoritmo no primeiro exemplo:

if __name__ == "__main__":
    W = [15, 10, 2, 4]
    V = [30, 25, 2, 6]
    M = 37
    n = 4

    proc = FractionalKnapsack()
    proc.knapsackGreProc(W, V, M, n)

C# Code para os Três Gananciosos

Definir o KnapsackPackage classe:

using System;

namespace KnapsackProblem
{
    public class KnapsackPackage
    {
        private double weight;
        private double value;
        private double cost;

        public KnapsackPackage(double weight, double value)
        {
            this.weight = weight;
            this.value  = value;
            this.cost   = value / weight;
        }

        public double Weight { get { return weight; } }
        public double Value  { get { return value; } }
        public double Cost   { get { return cost; } }
    }
}

Implemente o algoritmo Greedy Three com uma etapa de preenchimento fracionário:

public void KnapsackGreProc(int[] W, int[] V, int M, int n)
{
    KnapsackPackage[] packs = new KnapsackPackage[n];
    for (int k = 0; k < n; k++)
        packs[k] = new KnapsackPackage(W[k], V[k]);

    Array.Sort<KnapsackPackage>(packs,
        (a, b) => b.Cost.CompareTo(a.Cost));

    double remain = M;
    double result = 0d;

    for (int i = 0; i < n && remain > 0; i++)
    {
        if (packs[i].Weight <= remain)
        {
            remain -= packs[i].Weight;
            result += packs[i].Value;
            Console.WriteLine("Pack " + i + " - Weight " + packs[i].Weight
                            + " - Value " + packs[i].Value);
        }
        else
        {
            double fraction = remain / packs[i].Weight;
            result += packs[i].Value * fraction;
            Console.WriteLine("Pack " + i + " - Fraction " + fraction
                            + " - Value " + packs[i].Value * fraction);
            remain = 0;
        }
    }

    Console.WriteLine("Max Value:\t" + result);
}

Função KnapsackGreProc() em C#

Contraexemplo: Três Gananciosos em Mochila 0/1

O Ganancioso Três é ótimo para a variante Fracionária, mas pode ser superado na Mochila 0/1 (onde os itens não podem ser divididos). Contraexemplo:

• Parâmetros: n = 3, M = 10.
• Pacotes: {i = 1; W = 7; V = 9; custo = 9/7}, {i = 2; W = 6; V = 6; custo = 1}, {i = 3; W = 4; V = 4; custo = 1}.
• O método Greedy Three escolhe o pacote 1, que tem um valor total de 9, enquanto a escolha ideal 0/1 (pacote 2, pacote 3) atinge 10.

A lição: use o algoritmo Ganancioso Três somente quando frações forem permitidas. Para a variante 0/1, use Programaçao dinamica ao invés.

Aplicações da Mochila Fracionária

• Carregamento de carga onde mercadorias líquidas, em pó ou a granel podem ser divididas por peso.
• Alocação de portfólio entre opções de investimento que aceitam financiamento parcial.
• Compartilhamento de largura de banda na nuvem, onde os fluxos podem consumir uma fração de um link.
• Agendamento de CPU sob um modelo de fatiamento de tempo compartilhado com cargas de trabalho divisíveis.
• Alocação de recursos de IA onde uma tarefa de treinamento pode usar uma fração da GPU.

Perguntas Frequentes