Problema da mochila fracionada: algoritmo ganancioso com exemplo

O que é estratégia gananciosa?

Algoritmos gananciosos são como algoritmos de programação dinâmica que são frequentemente usados ​​para resolver problemas ótimos (encontrar as melhores soluções do problema de acordo com um critério específico).

Algoritmos gananciosos implementam seleções locais ótimas na esperança de que essas seleções levem a uma solução global ótima para o problema a ser resolvido. Algoritmos gananciosos muitas vezes não são muito difíceis de configurar, rápidos (tempo complex(idade é muitas vezes uma função linear ou uma função de segunda ordem). Além disso, esses programas não são difíceis de depurar e usam menos memória. Mas os resultados nem sempre são uma solução ideal.

Estratégias gananciosas são frequentemente usadas para resolver o problema de otimização combinatória construindo uma opção A. A opção A é construída selecionando cada componente Ai de A até completar (n componentes suficientes). Para cada Ai, você escolhe Ai de forma otimizada. Desta forma, é possível que na última etapa você não tenha nada para selecionar a não ser aceitar o último valor restante.

Existem dois componentes críticos de decisões gananciosas:

  1. Forma de seleção gananciosa. Você pode selecionar qual solução é a melhor no momento e então resolver o subproblema resultante da última seleção. A seleção de algoritmos gananciosos pode depender de seleções anteriores. Mas não pode depender de nenhuma seleção futura ou das soluções de subproblemas. O algoritmo evolui de forma a fazer seleções em loop, ao mesmo tempo que reduz o problema em questão a subproblemas menores.
  2. Subestrutura ideal. Você executa a subestrutura ótima para um problema se a solução ótima desse problema contiver soluções ótimas para seus subproblemas.

Um algoritmo ganancioso tem cinco componentes:

  1. Um conjunto de candidatos a partir dos quais criar soluções.
  2. Uma função de seleção, para selecionar o melhor candidato para adicionar à solução.
  3. Uma função viável é usada para decidir se um candidato pode ser usado para construir uma solução.
  4. Uma função objetivo, fixando o valor de uma solução ou de uma solução incompleta.
  5. Uma função de avaliação, indicando quando você encontra uma solução completa.

A ideia do ganancioso

Com a primeira ideia, você tem o seguintewing passos do Ganancioso:

  • Classifique em ordem não crescente de valores.
  • Por sua vez, considere os pacotes encomendados, coloque o pacote considerado na mochila se a capacidade restante da mochila for suficiente para contê-lo (o que significa que o peso total dos pacotes que foram colocados na mochila e o peso dos pacotes considerados não excedem a capacidade da mochila).

No entanto, este algoritmo ganancioso nem sempre fornece a solução ideal. Aqui você tem um contra-exemplo:

  • Os parâmetros do problema são: n = 3; M = 19.
  • Os pacotes: {i = 1; W[i] = 14; V[i] = 20}; {eu = 2; W[i] = 6; V[i] = 16}; {eu = 3; W[i] = 10; V[eu] = 8} -> Ótimo valor, mas também ótimo peso.
  • O algoritmo selecionará o pacote 1 com valor total de 20, enquanto a solução ótima do problema será selecionada (pacote 2, pacote 3) com valor total de 24.

A ideia dos dois gananciosos

Com a segunda ideia, você tem o seguintewing passos do Ganancioso Dois:

  • Classifique em ordem não decrescente de pesos.
  • Por sua vez, considere os pacotes encomendados, coloque o pacote considerado na mochila se a capacidade restante da mochila for suficiente para contê-lo (o que significa que o peso total dos pacotes que foram colocados na mochila e o peso dos pacotes considerados não excedem a capacidade da mochila).

No entanto, este algoritmo ganancioso nem sempre fornece a solução ideal. Aqui você tem um contra-exemplo:

  • Os parâmetros do problema são: n = 3; M = 11.
  • Os pacotes: {i = 1; W[i] = 5; V[i] = 10}; {eu = 2; W[i] = 6; V[i] = 16}; {eu = 3; W[i] = 10; V[eu] = 28} -> Peso leve, mas o valor também é muito leve.
  • O algoritmo selecionará (pacote 1, pacote 2) com valor total de 26, enquanto a solução ótima do problema é (pacote 3) com valor total de 28.

A ideia dos três gananciosos

Com a terceira ideia, você tem o seguintewing passos do Ganancioso Três. Na verdade, este é o algoritmo mais utilizado.

  • Classifique os pacotes em ordem não crescente do valor do custo unitário A ideia dos três gananciosos. Você tem:

A ideia dos três gananciosos

  • Por sua vez, considere os pacotes encomendados, coloque o pacote considerado na mochila se a capacidade restante da mochila for suficiente para contê-lo (o que significa que o peso total dos pacotes que foram colocados na mochila e o peso dos pacotes considerados não excedem a capacidade da mochila).

idéia: A ideia gananciosa desse problema é calcular o A ideia dos três gananciosos proporção de cada A ideia dos três gananciosos. Em seguida, classifique essas proporções em ordem decrescente. Você escolherá o mais alto A ideia dos três gananciosos pacote e a capacidade da mochila pode conter esse pacote (permanece > wi). Cada vez que um pacote é colocado na mochila, isso também reduz a capacidade da mochila.

Forma de selecionar os pacotes:

  • Considere a matriz de custos unitários. Você seleciona pacotes de acordo com custos unitários decrescentes.

A ideia dos três gananciosos

  • Suponha que você encontrou uma solução parcial: (x1,…, Xi).
  • O valor da mochila é obtido:

A ideia dos três gananciosos

  • Correspondente ao peso dos pacotes colocados na mochila:

A ideia dos três gananciosos

  • Portanto, o limite de peso restante da mochila é:

A ideia dos três gananciosos

Etapas do Algoritmo

Você vê que este é um problema de encontrar o máximo. A lista de pacotes é classificada em ordem decrescente de custos unitários para considerar a ramificação.

  • Passo 1: O nó raiz representa o estado inicial da mochila, onde você não selecionou nenhum pacote.
  • ValorTotal = 0.
  • O limite superior do nó raiz UpperBound = M * Custo unitário máximo.
  • Passo 2: O nó raiz terá nós filhos correspondentes à capacidade de selecionar o pacote com o maior custo unitário. Para cada nó, você recalcula os parâmetros:
  • TotalValue = TotalValue (antigo) + número de pacotes selecionados * valor de cada pacote.
  • M = M (antigo) – quantidade de embalagens selecionadas * peso de cada embalagem.
  • UpperBound = TotalValue + M (novo) * O custo unitário do pacote a ser considerado a seguir.
  • Passo 3: em nós filhos, você priorizará a ramificação para o nó que tiver o limite superior maior. Os filhos deste nó correspondem à capacidade de selecionar o próximo pacote de grande custo unitário. Para cada nó, deve-se recalcular os parâmetros TotalValue, M, UpperBound conforme fórmula citada no passo 2.
  • Passo 4: Repita a Etapa 3 com a observação: para nós com limite superior com valores inferiores ou iguais ao custo máximo temporário de uma opção encontrada, você não precisa mais ramificar para esse nó.
  • Passo 5: Se todos os nós estiverem ramificados ou cortados, a opção mais cara é a que deve ser procurada.

Pseudocódigo para o algoritmo:

Fractional Knapsack (Array W, Array V, int M)
1. for i <- 1 to size (V)
2. 	calculate cost[i] <- V[i] / W[i]
3. Sort-Descending (cost)
4. i ← 1
5. while (i <= size(V))
6. 	if  W[i] <= M 
7.		M ← M – W[i]
8.		total ← total + V[i];
9. 	if  W[i] > M
10. 		i ← i+1

O complexqualidade do algoritmo:

  • Se estiver usando um algoritmo de classificação simples (seleção, bolha…), então o complexA qualidade de todo o problema é O(n2).
  • Se estiver usando classificação rápida ou classificação por mesclagem, o complexA qualidade de todo o problema é O(nlogn).

Código Java para Greedy Three

  • Primeiramente, você define a classe KnapsackPackage. Esta classe possui propriedades que são: peso, valor e custo correspondente de cada pacote. O custo da propriedade desta classe é usado para classificar tarefas no algoritmo principal. O valor de cada custo é o Ganancioso Três proporção de cada pacote.
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 = new Double(value / weight);
	}

	public double getWeight() {
		return weight;
	}

	public double getValue() {
		return value;
	}

	public Double getCost() {
		return cost;
	}

}
  • Você então cria uma função para executar 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 kPackA, KnapsackPackage kPackB) {
			return kPackB.getCost().compareTo(kPackA.getCost());
		}
	});
	
	int remain = M;	
double result = 0d;
	
	int i = 0;
	boolean stopProc = false;
	while (!stopProc) {
		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());
		}
		
		if (packs[i].getWeight() > remain) {
			i ++;
		}
		
		if (i == n) {
			stopProc = true;
		}
	}
	
	System.out.println("Max Value:\t" + result);
}
Função mochilaGreProc() em Java
Função mochilaGreProc() em Java

Explicação do código:

  1. Inicialize o peso e o valor de cada pacote de mochila.
  2. Classifique os pacotes de mochila por custo em ordem decrescente.
  3. Se selecionar o pacote i.
  4. Se selecionar o número do pacote i é suficiente.
  5. Pare ao navegar em todos os pacotes.

Neste tutorial, você tem dois exemplos. Aqui está o código java para executar o programa acima com dois exemplos:

public void run() {
	/*
	 * Pack and Weight - Value
	 */
//int W[] = new int[]{15, 10, 2, 4};
	int W[] = new int[]{12, 2, 1, 1, 4};
	
//int V[] = new int[]{30, 25, 2, 6};
	int V[] = new int[]{4, 2, 1, 2, 10};
	
	/*
	 * Max Weight
	 */
//int M = 37;
	int M = 15;
	int n = V.length;
	
	/*
	 * Run the algorithm
	 */
	knapsackGreProc(W, V, M, n);
}

Você tem a saída:

  • Primeiro exemplo:
Pack 0 - Weight 10.0 - Value 25.0
Pack 0 - Weight 10.0 - Value 25.0
Pack 0 - Weight 10.0 - Value 25.0
Pack 2 - Weight 4.0 - Value 6.0
Pack 3 - Weight 2.0 - Value 2.0
Max Value:	83.0
  • Segundo exemplo:
Pack 0 - Weight 4.0 - Value 10.0
Pack 0 - Weight 4.0 - Value 10.0
Pack 0 - Weight 4.0 - Value 10.0
Pack 1 - Weight 1.0 - Value 2.0
Pack 1 - Weight 1.0 - Value 2.0
Pack 1 - Weight 1.0 - Value 2.0
Max Value:	36.0

Analise o primeiro exemplo:

  • Os parâmetros do problema são: n = 4; M = 37.
  • Os pacotes: {i = 1; W[i] = 15; V[i] = 30; Custo = 2.0}; {eu = 2; W[i] = 10; V[i] = 25; Custo = 2.5}; {eu = 3; W[i] = 2; V[i] = 4; Custo = 1.0}; {eu = 4; W[i] = 4; V[i] = 6; Custo = 1.5}.
  • Você classifica os pacotes em ordem sem aumento do valor dos custos unitários. Você tem: {i = 2} -> {eu = 1} -> {eu = 4} -> {eu = 3}.

Etapas para aplicar o algoritmo para o primeiro exemplo:

  • Defina x1, x2, x3, x4 é o número de cada pacote selecionado, correspondente ao pacote {i = 2} -> {eu = 1} -> {eu = 4} -> {eu = 3}.
  • A raiz do nó N representa o estado em que você não selecionou nenhum pacote. Então:
    • ValorTotal = 0.
    • M = 37 (conforme proposto).
    • UpperBound = 37 * 2.5 = 92.5, dos quais 37 é M e 2.5 é o custo unitário do pacote {i = 2}.
  • Com o pacote {i = 2}, você tem 4 possibilidades: selecione 3 pacotes {i = 2} (x1 = 3); selecione 2 pacotes {i = 2} (x1 = 2); selecione 1 pacote {i = 2} (x1 = 1) e não selecione o pacote {i = 2} (x1 = 0). De acordo com essas 4 possibilidades, você ramifica o nó raiz N para 4 filhos N[1], N[2], N[3] e N[4].
  • Para o nó filho N1, você tem:
    • TotalValue = 0 + 3 * 25 = 75, onde 3 é o número de pacotes {i = 2} selecionados e 25 é o valor de cada pacote {i = 2}.
    • M = 37 – 3 * 10 = 7, onde 37 é a quantidade inicial da mochila, 3 é o número do pacote {i = 2}, 10 é o peso de cada pacote {i = 2}.
    • UpperBound = 75 + 7 * 2 = 89, onde 75 é TotalValue, 7 é o peso restante da mochila e 2 é o custo unitário do pacote {i = 1}.
  • Da mesma forma, você pode calcular os parâmetros para os nós N[2], N[3] e N[4], nos quais o UpperBound é 84, 79 e 74 respectivamente.
  • Entre os nós N[1], N[2], N[3] e N[4], o nó N[1] tem o maior UpperBound, então você ramificará o nó N[1] primeiro na esperança de que haja um bom plano desta direção.
  • Do nó N[1], você tem apenas um nó filho N[1-1] correspondente a x2 = 0 (devido ao peso restante da mochila ser 7, enquanto o peso de cada pacote {i = 1} é 15) . Depois de determinar os parâmetros para o botão N[1-1], você terá que o UpperBound de N[1-1] é 85.5.
  • Você continua ramificando o nó N[1-1]. O nó N[1-1] tem 2 filhos N[1-1-1] e N[1-1-2] correspondentes a x3 = 1 e x3 = 0. Depois de determinar os parâmetros para esses dois nós, você vê que o UpperBoundary de N[1-1-1] é 84 e o de N[1-1-2] é 82, então você continua ramificando o nó N[1-1-1].
  • O nó N[1-1-1] tem dois filhos, N[1-1-1-1] e N[1-1-1-2], correspondendo a x4 = 1 e x4 = 0. Estes são dois nós folha (representando a opção) porque para cada nó foi selecionado o número de pacotes. Em que o nó N[1-1-1-1] representa a opção x1 = 3, x2 = 0, x3 = 1 e x4 = 1 para 83, enquanto o nó N[1-1-1-2] representa a opção x1 = 3, x2 = 0, x3 = 1 e x4 = 01 em 81. Portanto, o valor máximo temporário aqui é 83.
  • Voltando ao nó N[1-1-2], você vê que o UpperBound de N[1-1-2] é 82 <83, então você corta o nó N[1-1-2].
  • Voltando ao nó N2, você vê que o UpperBound de N2 é 84> 83, então continua ramificando o nó N2. O nó N2 tem dois filhos N[2-1] e N[2-2] correspondentes a x2 = 1 e x2 = 0. Depois de calcular os parâmetros para N[2-1] e N[2-2], você vê o limite superior de N[2-1] é 83 e o de N[2-2] é 75.25. Nenhum desses valores é maior que 83, portanto ambos os nós são cortados.
  • Finalmente, os nós N3 e N4 também são cortados.
  • Assim, todos os nós da árvore são ramificados ou aparados, de modo que a melhor solução temporária é aquela a ser procurada. Assim, você precisa selecionar 3 pacotes {i = 2}, 1 pacote {i = 4} e um pacote {i = 3} com valor total de 83, o peso total é 36.

Com a mesma análise do segundo exemplo, você tem o resultado: selecione o pacote 4 (3 vezes) e o pacote 5 (3 vezes).

Código Python3 para Greedy Three

  • Primeiramente, você define a classe KnapsackPackage.
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
  • Você então cria uma função para executar o algoritmo Greedy Three.
class FractionalKnapsack(object):
    def __init__(self):
        
    def knapsackGreProc(self, W, V, M, n):
        packs = []
        for i in range(n): 
            packs.append(KnapsackPackage(W[i], V[i]))
            
        packs.sort(reverse = True)
        
        remain = M
        result = 0
        
        i = 0
        stopProc = False
        
        while (stopProc != True):
            if (packs[i].weight <= remain):
                remain -= packs[i].weight;
                result += packs[i].value;
                
                print("Pack ", i, " - Weight ", packs[i].weight, " - Value ", packs[i].value)
            
            if (packs[i].weight > remain):
                i += 1
                
            if (i == n):
                stopProc = True            
        
        print("Max Value:\t", result)   
Função mochilaGreProc() em Python
Função mochilaGreProc() em Python

Explicação do código:

  1. Inicialize o peso e o valor de cada pacote de mochila.
  2. Classifique os pacotes de mochila por custo em ordem decrescente.
  3. Se selecionar o pacote i.
  4. Se selecionar o número do pacote i é suficiente.
  5. Pare ao navegar em todos os pacotes.

Aqui está o código Python3 para executar o programa acima com o 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)

Você tem a saída:

Pack  0  - Weight  10  - Value  25
Pack  0  - Weight  10  - Value  25
Pack  0  - Weight  10  - Value  25
Pack  2  - Weight  4  - Value  6
Pack  3  - Weight  2  - Value  2
Max Value:	 83

Código C# para Greedy Three

  • Primeiramente, você define a classe KnapsackPackage.
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 = (double) value / weight;
        }

        public double Weight
        {
            get { return weight; }
        }

        public double Value
        {
            get { return value; }
        }

        public double Cost
        {
            get { return cost; }
        }
    }
}
  • Você então cria uma função para executar o algoritmo Greedy Three.
using System;
namespace KnapsackProblem
{
    public class FractionalKnapsack
    {
        public FractionalKnapsack()
        {
        }

        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, new Comparison<KnapsackPackage>(
                 (kPackA, kPackB) => kPackB.Cost.CompareTo(kPackA.Cost)));

            double remain = M;
            double result = 0d;

            int i = 0;
            bool stopProc = false;

            while (!stopProc)
            {
                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);
                }

                if (packs[i].Weight > remain)
                {
                    i++;
                }

                if (i == n)
                {
                    stopProc = true;
                }
            }

            Console.WriteLine("Max Value:\t" + result);
        }        
    }
}
Função KnapsackGreProc() em C#
Função KnapsackGreProc() em C#

Explicação do código:

  1. Inicialize o peso e o valor de cada pacote de mochila.
  2. Classifique os pacotes de mochila por custo em ordem decrescente.
  3. Se selecionar o pacote i.
  4. Se selecionar o número do pacote i é suficiente.
  5. Pare ao navegar em todos os pacotes.

Aqui está o código C# para executar o programa acima com o primeiro exemplo:

public void run()
{
    /*
     * Pack and Weight - Value
     */
    int[] W = new int[]{15, 10, 2, 4};
    //int[] W = new int[] { 12, 2, 1, 1, 4 };

    int[] V = new int[]{30, 25, 2, 6};
    //int[] V = new int[] { 4, 2, 1, 2, 10 };

    /*
     * Max Weight
     */
    int M = 37;
    //int M = 15;
    int n = V.Length;

    /*
     * Run the algorithm
     */
    KnapsackGreProc(W, V, M, n);
}

Você tem a saída:

Pack 0 - Weight 10 - Value 25
Pack 0 - Weight 10 - Value 25
Pack 0 - Weight 10 - Value 25
Pack 2 - Weight 4 - Value 6
Pack 3 - Weight 2 - Value 2
Max Value:	83

Contra-exemplo de Greedy Three

O algoritmo do Greedy Three é resolvido rapidamente e também pode ser ideal em alguns casos. Contudo, em alguns casos especiais, não fornece a solução ideal. Aqui você tem um contra-exemplo:

  • Os parâmetros do problema são: n = 3; M = 10.
  • Os pacotes: {i = 1; W[i] = 7; V[i] = 9; Custo = 9/7}; {eu = 2; W[i] = 6; V[i] = 6; Custo = 1}; {eu = 3; W[i] = 4; V[i] = 4; Custo = 1}.
  • O algoritmo selecionará (pacote 1) com valor total de 9, enquanto a solução ótima do problema será (pacote 2, pacote 3) com valor total de 10.

Aqui está o código java para executar o programa acima com o contra-exemplo:

public void run() {
	/*
	 * Pack and Weight - Value
	 */
	int W[] = new int[]{7, 6, 4};
	
	int V[] = new int[]{9, 6, 4};
	
	/*
	 * Max Weight
	 */
	int M = 10;
	int n = V.length;
	
	/*
	 * Run the algorithm
	 */
	knapsackGreProc(W, V, M, n);
}

Aqui está o resultado:

Pack 0 - Weight 7.0 - Value 9.0
Max Value:	9.0

Isso é tudo para o problema da mochila fracionária.