Problema de mochila fraccional: Algoritmo codicioso con ejemplo
sarah chen
¿Qué es la estrategia codiciosa?
Los algoritmos voraces son como algoritmos de programación dinámica que a menudo se utilizan para resolver problemas óptimos (encontrar las mejores soluciones del problema según un criterio particular).
Los algoritmos voraces implementan selecciones locales óptimas con la esperanza de que esas selecciones conduzcan a una solución global óptima para el problema que se desea resolver. Los algoritmos voraces no suelen ser demasiado difíciles de configurar y son rápidos (la complejidad temporal suele ser una función lineal o una función de segundo orden). Además, estos programas no son difíciles de depurar y utilizan menos memoria, pero los resultados no siempre son una solución óptima.
Las estrategias codiciosas se utilizan a menudo para resolver el problema de optimización combinatoria construyendo una opción A. La opción A se construye seleccionando cada componente Ai de A hasta que esté completa (suficientes n componentes). Para cada Ai, eliges Ai de manera óptima. De esta forma, es posible que en el último paso no tengas nada que seleccionar más que aceptar el último valor restante.
Hay dos componentes críticos de las decisiones codiciosas:
- Método de selección voraz. Se puede seleccionar la mejor solución en el momento actual y luego resolver el subproblema que surge de la última selección. La selección de algoritmos voraces puede depender de selecciones anteriores, pero no de ninguna selección futura ni de las soluciones de subproblemas. El algoritmo evoluciona de manera que realiza selecciones en un bucle, al mismo tiempo que reduce el problema dado a subproblemas más pequeños.
- Subestructura óptima. Se realiza la subestructura óptima para un problema si la solución óptima de este problema contiene soluciones óptimas para sus subproblemas.
Un algoritmo codicioso tiene cinco componentes:
- Un conjunto de candidatos, a partir de los cuales crear soluciones.
- Una función de selección, para seleccionar el mejor candidato para agregar a la solución.
- Se utiliza una función factible para decidir si un candidato se puede utilizar para construir una solución.
- Una función objetivo, que fija el valor de una solución o una solución incompleta.
- Una función de evaluación, que indica cuándo encuentra una solución completa.
La idea del codicioso
Con la primera idea, tienes los siguientes pasos de Greedy One:
- Ordenar en orden no creciente de valores.
- A su vez, considere los paquetes ordenados, coloque el paquete en cuestión en la mochila si la capacidad restante de la mochila es suficiente para contenerlo (lo que significa que el peso total de los paquetes que se han puesto en la mochila y el peso de los paquetes en consideración no exceden la capacidad de la mochila).
Sin embargo, este codicioso algoritmo no siempre da la solución óptima. Aquí tienes un contraejemplo:
- Los parámetros del problema son: n = 3; M = 19.
- Los paquetes: {i = 1; W[yo] = 14; V[yo] = 20}; {yo = 2; W[yo] = 6; V[yo] = 16}; {yo = 3; W[yo] = 10; V[yo] = 8} -> Gran valor pero también gran peso.
- El algoritmo seleccionará el paquete 1 con un valor total de 20, mientras que se selecciona la solución óptima del problema (paquete 2, paquete 3) con un valor total de 24.
La idea de los dos codiciosos
Con la segunda idea tienes los siguientes pasos de Greedy Two:
- Ordene en orden no decreciente de pesos.
- A su vez, considere los paquetes ordenados, coloque el paquete en cuestión en la mochila si la capacidad restante de la mochila es suficiente para contenerlo (lo que significa que el peso total de los paquetes que se han puesto en la mochila y el peso de los paquetes en consideración no exceden la capacidad de la mochila).
Sin embargo, este codicioso algoritmo no siempre da la solución óptima. Aquí tienes un contraejemplo:
- Los parámetros del problema son: n = 3; M = 11.
- Los paquetes: {i = 1; W[yo] = 5; V[yo] = 10}; {yo = 2; W[yo] = 6; V[yo] = 16}; {yo = 3; W[yo] = 10; V[yo] = 28} -> Peso ligero pero el valor también es muy ligero.
- El algoritmo seleccionará (paquete 1, paquete 2) con un valor total de 26, mientras que la solución óptima del problema es (paquete 3) con un valor total de 28.
La idea de los tres codiciosos
Con la tercera idea, tienes los siguientes pasos de Greedy Three. De hecho, este es el algoritmo más utilizado.
- Clasificar los paquetes en orden de no aumentar el valor del costo unitario.
. Tu tienes:
- A su vez, considere los paquetes ordenados, coloque el paquete en cuestión en la mochila si la capacidad restante de la mochila es suficiente para contenerlo (lo que significa que el peso total de los paquetes que se han puesto en la mochila y el peso de los paquetes en consideración no exceden la capacidad de la mochila).
Idea: La idea codiciosa de ese problema es calcular el 
proporción de cada 
. Luego ordena estas proporciones en orden descendente. elegirás el más alto paquete y la capacidad de la mochila puede contener ese paquete (permanecer > wi). Cada vez que se coloca un paquete en la mochila, también se reducirá la capacidad de la mochila.
Forma de seleccionar los paquetes:
- Considere la variedad de costos unitarios. Usted selecciona paquetes de acuerdo con costos unitarios decrecientes.
- Supongamos que encuentras una solución parcial: (x1,…, Xi).
- El valor de la mochila se obtiene:
- Correspondiente al peso de los bultos que se han metido en la mochila:
- Por tanto, el límite de peso restante de la mochila es:
Pasos del algoritmo
Verás, este es un problema de encontrar max. La lista de paquetes está ordenada en orden descendente de costos unitarios para considerar la ramificación.
- Paso 1: La raíz del nodo representa el estado inicial de la mochila, donde no se ha seleccionado ningún paquete.
- Valor total = 0.
- El límite superior del nodo raíz UpperBound = M * Costo unitario máximo.
- Paso 2: La raíz del nodo tendrá nodos secundarios correspondientes a la capacidad de seleccionar el paquete con el mayor costo unitario. Para cada nodo, vuelve a calcular los parámetros:
- ValorTotal = ValorTotal (antiguo) + número de paquetes seleccionados * valor de cada paquete.
- M = M (antiguo) – número de paquetes seleccionados * peso de cada paquete.
- UpperBound = TotalValue + M (nuevo) * El costo unitario del paquete que se considerará a continuación.
- Paso 3: En los nodos secundarios, dará prioridad a la ramificación del nodo que tenga el límite superior más grande. Los hijos de este nodo corresponden a la capacidad de seleccionar el siguiente paquete que tiene un costo unitario grande. Para cada nodo, debe volver a calcular los parámetros TotalValue, M, UpperBound según la fórmula mencionada en el paso 2.
- Paso 4: Repita el paso 3 con la nota: para los nodos con límite superior con valores inferiores o iguales al costo máximo temporal de una opción encontrada, ya no necesita bifurcarse para ese nodo.
- Paso 5: Si todos los nodos están ramificados o cortados, la opción más cara es la que hay que buscar.
Pseudocódigo para el 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
La complejidad del algoritmo:
- Si se utiliza un algoritmo de ordenamiento simple (selección, burbuja…) entonces la complejidad de todo el problema es O(n2).
- Si se utiliza la ordenación rápida o la ordenación por combinación, la complejidad de todo el problema es O(nlogn).
Java código para los tres codiciosos
- En primer lugar, define la clase KnapsackPackage. Esta clase tiene propiedades que son: peso, valor y costo correspondiente de cada paquete. El costo de propiedad de esta clase se utiliza para ordenar tareas en el algoritmo principal. El valor de cada costo es el
proporción de cada paquete.
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;
}
}
- Luego crea una función para realizar el 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);
}
Explicación del código:
- Inicialice el peso y el valor de cada paquete de mochila.
- Ordene los paquetes de mochilas por costo en orden descendente.
- Si selecciona el paquete i.
- Si selecciona el número de paquete i es suficiente.
- Deténgase al explorar todos los paquetes.
En este tutorial tienes dos ejemplos. Aquí hay código Java para ejecutar el programa anterior con dos ejemplos:
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);
}
Tienes la salida:
- Primer ejemplo:
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 ejemplo:
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
Analice el primer ejemplo:
- Los parámetros del problema son: n = 4; M = 37.
- Los paquetes: {i = 1; W[yo] = 15; V[yo] = 30; Costo = 2.0}; {yo = 2; W[yo] = 10; V[yo] = 25; Costo = 2.5}; {yo = 3; W[yo] = 2; V[yo] = 4; Costo = 1.0}; {yo = 4; W[yo] = 4; V[yo] = 6; Costo = 1.5}.
- Los paquetes se clasifican en orden sin aumentar el valor de los costos unitarios. Tienes: {i = 2} -> {yo = 1} -> {yo = 4} -> {yo = 3}.
Pasos para aplicar el algoritmo para el primer ejemplo:
- Definir x1, x2, x3, x4 es el número de cada paquete seleccionado, correspondiente al paquete {i = 2} -> {yo = 1} -> {yo = 4} -> {yo = 3}.
- La raíz del nodo N representa el estado en el que no ha seleccionado ningún paquete. Entonces:
- Valor total = 0.
- M = 37 (según lo propuesto).
- UpperBound = 37 * 2.5 = 92.5, de los cuales 37 es M y 2.5 es el costo unitario del paquete {i = 2}.
- Con el paquete {i = 2}, tienes 4 posibilidades: selecciona 3 paquetes {i = 2} (x1 = 3); seleccione 2 paquetes {i = 2} (x1 = 2); seleccione 1 paquete {i = 2} (x1 = 1) y no seleccione el paquete {i = 2} (x1 = 0). De acuerdo con estas 4 posibilidades, bifurca el nodo raíz N en 4 hijos N[1], N[2], N[3] y N[4].
- Para el nodo secundario N1, tienes:
- TotalValue = 0 + 3 * 25 = 75, donde 3 es el número de paquete {i = 2} seleccionado y 25 es el valor de cada paquete {i = 2}.
- M = 37 – 3 * 10 = 7, donde 37 es la cantidad inicial de la mochila, 3 es el número de bultos {i = 2}, 10 es el peso de cada bulto {i = 2}.
- UpperBound = 75 + 7 * 2 = 89, donde 75 es TotalValue, 7 es el peso restante de la mochila y 2 es el costo unitario del paquete {i = 1}.
- De manera similar, puede calcular los parámetros para los nodos N[2], N[3] y N[4], en los que el límite superior es 84, 79 y 74 respectivamente.
- Entre los nodos N[1], N[2], N[3] y N[4], el nodo N[1] tiene el límite superior más grande, por lo que primero bifurcará el nodo N[1] con la esperanza de que haya un Buen plan desde esta dirección.
- Del nodo N[1], tienes solo un nodo hijo N[1-1] correspondiente a x2 = 0 (debido a que el peso restante de la mochila es 7, mientras que el peso de cada paquete {i = 1} es 15) . Después de determinar los parámetros para el botón N[1-1], el límite superior de N[1-1] es 85.5.
- Continúa ramificando el nodo N[1-1]. El nodo N[1-1] tiene 2 hijos N[1-1-1] y N[1-1-2] correspondientes a x3 = 1 y x3 = 0. Después de determinar los parámetros para estos dos nodos, verá que el El límite superior de N[1-1-1] es 84 y el de N[1-1-2] es 82, por lo que continúa ramificando el nodo N[1-1-1].
- El nodo N[1-1-1] tiene dos hijos, N[1-1-1-1] y N[1-1-1-2], correspondientes a x4 = 1 y x4 = 0. Estos son dos nodos hoja. (que representa la opción) porque para cada nodo se ha seleccionado el número de paquetes. En el cual el nodo N[1-1-1-1] representa la opción x1 = 3, x2 = 0, x3 = 1 y x4 = 1 para 83, mientras que el nodo N[1-1-1-2] representa la opción x1 = 3, x2 = 0, x3 = 1 y x4 = 01 en 81. Entonces el valor máximo temporal aquí es 83.
- Volviendo al nodo N[1-1-2], verá que el límite superior de N[1-1-2] es 82 < 83, por lo que recortará el nodo N[1-1-2].
- Volviendo al nodo N2, verá que el límite superior de N2 es 84 > 83, por lo que continúa ramificando el nodo N2. El nodo N2 tiene dos hijos N[2-1] y N[2-2] correspondientes a x2 = 1 y x2 = 0. Después de calcular los parámetros para N[2-1] y N[2-2], verá el límite superior de N[2-1] es 83 y el de N[2-2] es 75.25. Ninguno de estos valores es mayor que 83, por lo que se recortan ambos nodos.
- Finalmente, también se recortan los nodos N3 y N4.
- Entonces todos los nodos del árbol se ramifican o recortan para que la mejor solución temporal sea la que hay que buscar. En consecuencia, debe seleccionar 3 paquetes {i = 2}, 1 paquete {i = 4} y un paquete {i = 3} con un valor total de 83 y un peso total de 36.
Con el mismo análisis del segundo ejemplo, tienes el resultado: selecciona el paquete 4 (3 veces) y el paquete 5 (3 veces).
PythonCódigo 3 para los tres codiciosos
- En primer lugar, define la clase 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
- Luego crea una función para realizar el 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)
Explicación del código:
- Inicialice el peso y el valor de cada paquete de mochila.
- Ordene los paquetes de mochilas por costo en orden descendente.
- Si selecciona el paquete i.
- Si selecciona el número de paquete i es suficiente.
- Deténgase al explorar todos los paquetes.
Esta es Python3 código para ejecutar el programa anterior con el primer ejemplo:
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)
Tienes la salida:
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
- En primer lugar, define la clase 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; }
}
}
}
- Luego crea una función para realizar el 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);
}
}
}
Explicación del código:
- Inicialice el peso y el valor de cada paquete de mochila.
- Ordene los paquetes de mochilas por costo en orden descendente.
- Si selecciona el paquete i.
- Si selecciona el número de paquete i es suficiente.
- Deténgase al explorar todos los paquetes.
Aquí está el código C# para ejecutar el programa anterior con el primer ejemplo:
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);
}
Tienes la salida:
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
Contraejemplo de Greedy Three
El algoritmo de Greedy Three se resuelve rápidamente y también puede ser óptimo en algunos casos. Sin embargo, en algunos casos especiales, no ofrece la solución óptima. Aquí tienes un contraejemplo:
- Los parámetros del problema son: n = 3; M = 10.
- Los paquetes: {i = 1; W[yo] = 7; V[yo] = 9; Costo = 9/7}; {yo = 2; W[yo] = 6; V[yo] = 6; Costo = 1}; {yo = 3; W[yo] = 4; V[yo] = 4; Costo = 1}.
- El algoritmo seleccionará (paquete 1) con un valor total de 9, mientras que la solución óptima del problema es (paquete 2, paquete 3) con un valor total de 10.
Aquí está el código Java para ejecutar el programa anterior con el contraejemplo:
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);
}
Aquí está el resultado:
Pack 0 - Weight 7.0 - Value 9.0 Max Value: 9.0
Eso es todo sobre el problema de la mochila fraccionaria.
