Problema da mochila fracionada: algoritmo ganancioso com exemplo
Sarah Chen
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 geralmente não são muito difíceis de configurar e são rápidos (a complexidade do tempo costuma ser uma função linear ou, em grande parte, 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:
- 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.
- 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:
- Um conjunto de candidatos a partir dos quais criar soluções.
- Uma função de seleção, para selecionar o melhor candidato para adicionar à solução.
- Uma função viável é usada para decidir se um candidato pode ser usado para construir uma solução.
- Uma função objetivo, fixando o valor de uma solução ou de uma solução incompleta.
- Uma função de avaliação, indicando quando você encontra uma solução completa.
A ideia do ganancioso
Com a primeira ideia, você tem os seguintes passos do Greedy One:
- 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 as seguintes etapas do Greedy Two:
- 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 as seguintes etapas do Greedy Three. Na verdade, este é o algoritmo mais utilizado.
- Classifique os pacotes em ordem não crescente do valor do custo unitário
. Você tem:
- 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 
proporção de cada 
. Em seguida, classifique essas proporções em ordem decrescente. Você escolherá o mais alto 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.
- Suponha que você encontrou uma solução parcial: (x1,…, Xi).
- O valor da mochila é obtido:
- Correspondente ao peso dos pacotes colocados na mochila:
- Portanto, o limite de peso restante da mochila é:
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
A complexidade do algoritmo:
- Se estiver usando um algoritmo de classificação simples (seleção, bolha…), então a complexidade de todo o problema é O(n2).
- Se estiver usando classificação rápida ou classificação por mesclagem, a complexidade de todo o problema é O (nlogn).
Java código para três gananciosos
- 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
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);
}
Explicação do código:
- Inicialize o peso e o valor de cada pacote de mochila.
- Classifique os pacotes de mochila por custo em ordem decrescente.
- Se selecionar o pacote i.
- Se selecionar o número do pacote i é suficiente.
- 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).
Python3 código para Três gananciosos
- 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)
Explicação do código:
- Inicialize o peso e o valor de cada pacote de mochila.
- Classifique os pacotes de mochila por custo em ordem decrescente.
- Se selecionar o pacote i.
- Se selecionar o número do pacote i é suficiente.
- Pare ao navegar em todos os pacotes.
Aqui está Python3 código 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);
}
}
}
Explicação do código:
- Inicialize o peso e o valor de cada pacote de mochila.
- Classifique os pacotes de mochila por custo em ordem decrescente.
- Se selecionar o pacote i.
- Se selecionar o número do pacote i é suficiente.
- 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.
