Problema de mochila fraccional: Algoritmo codicioso con ejemplo

¿Qué es la estrategia codiciosa?

Algoritmos codiciosos En cada paso, eligen la mejor opción local con la esperanza de que una cadena de óptimos locales produzca una solución óptima global. Al igual que la programación dinámica, se centran en problemas de optimización, pero nunca revisan decisiones anteriores.

Los algoritmos voraces suelen ser sencillos de escribir, rápidos (a menudo con tiempo lineal o cuadrático), fáciles de depurar y consumen poca memoria. La desventaja es que el resultado no siempre es óptimo, por lo que esta estrategia solo funciona para problemas con una estructura que ha demostrado ser segura para algoritmos voraces.

Las estrategias voraces resuelven la optimización combinatoria construyendo una solución A, un componente Ai a la vez. En cada paso, se elige Ai de forma óptima bajo las restricciones actuales y se reduce el problema a un subproblema más pequeño.

Para que un método voraz sea correcto, deben cumplirse dos propiedades:

1. Propiedad de elección codiciosa: Un óptimo local en cada paso conduce a un óptimo global. La elección depende de decisiones pasadas, pero no de decisiones futuras.
2. Subestructura óptima: La solución óptima del problema completo contiene las soluciones óptimas de sus subproblemas.

Un algoritmo codicioso tiene cinco componentes:

1. Un conjunto de candidatos a partir del cual se construyen soluciones.
2. Una función de selección que elige al mejor candidato para el siguiente paso.
3. Una función de viabilidad que comprueba si un candidato puede ampliar la solución parcial actual.
4. Una función objetivo que valora una solución completa o parcial.
5. Una función de evaluación que indica cuándo se ha completado la solución.

La idea del codicioso

Greedy One clasifica los paquetes únicamente por su valor:

• Ordena los paquetes en orden descendente de valor.
• Recorre la lista ordenada y añade cada paquete a la mochila si la capacidad restante lo permite.

Esta regla no siempre da la respuesta óptima. Contraejemplo:

• Parámetros: n = 3, M = 19.
• Paquetes: {i = 1; W = 14; V = 20}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 8} — alto valor pero también alto peso.
• El usuario Greedy One elige el paquete 1 con un valor total de 20, mientras que la elección óptima (paquete 2, paquete 3) alcanza los 24.

La idea de los dos codiciosos

Greedy Two clasifica los paquetes únicamente por peso:

• Clasifique los paquetes en orden no decreciente de peso.
• Recorre la lista ordenada y añade cada paquete a la mochila si la capacidad restante lo permite.

Esta regla tampoco es óptima. Contraejemplo:

• Parámetros: n = 3, M = 11.
• Paquetes: {i = 1; W = 5; V = 10}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 28} — peso ligero pero bajo valor.
• El algoritmo Greedy Two elige (paquete 1, paquete 2) con un valor total de 26, mientras que la elección óptima (paquete 3) alcanza 28.

La idea de los tres codiciosos

El algoritmo Greedy Three corrige ambos fallos combinando valor y peso en una única clave de clasificación. Es el método estándar para el problema de la mochila fraccionaria.

• Calcula el costo unitario V[i] / W[i] para cada paquete.
• Clasifique los paquetes en orden descendente según su costo unitario.
• Recorre la lista ordenada y añade cada paquete si la capacidad restante lo permite.

Tres algoritmos codiciosos se clasifican por costo unitario V[i] / W[i]

Idea: Calcula la relación valor-peso V[i] / W[i] para cada paquete, ordénalos en orden descendente y toma primero la relación más grande disponible hasta que la mochila esté llena.

por la verdad Fraccionario En esta variante, cuando el siguiente paquete no cabe completo, se toma una fracción que llena exactamente la capacidad restante. Esta regla adicional es lo que hace que el algoritmo Greedy Three sea demostrablemente óptimo en el problema de la mochila fraccionaria.

Pasos del algoritmo

Para la variante de ramificación y acotación 0/1, la lista de costos unitarios ordenada impulsa un árbol de búsqueda:

• Paso 1: El nodo raíz representa una mochila vacía. TotalValue = 0. UpperBound = M × coste unitario máximo.
• Paso 2: Ramifique la raíz según cuántas copias del paquete de mayor proporción puedan caber. Para cada hijo, vuelva a calcular TotalValue, la capacidad restante M y UpperBound.
• Paso 3: Primero, expanda el elemento hijo con el límite superior más grande, con la esperanza de encontrar rápidamente una solución sólida.
• Paso 4: Pode cualquier nodo cuyo límite superior no sea mejor que la mejor solución completa actual.
• Paso 5: Cuando cada nodo se expande o se poda, la mejor solución completa actual es la óptima.

Pseudocódigo para el algoritmo voraz de la mochila fraccionaria 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

Complejidad del algoritmo:

• Usando una ordenación simple (selección o burbuja): O(n²).
• Usando ordenación rápida o ordenación por fusión: O(n log n), dominado por el paso de ordenación.

Java Code para Greedy Three

Definir el KnapsackPackage Clase con peso, valor y costo derivado (la relación V/W utilizada para la clasificación):

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; }
}

Luego, crea la función que implementa 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);
}

Función mochilaGreProc() en Java

Explicación del código:

1. Envuelva cada entrada en un KnapsackPackage Por lo tanto, la clave de ordenación (relación V/W) se calcula previamente.
2. Ordenar en orden descendente de costo.
3. Coge cada paquete entero si cabe.
4. Toma una fracción del siguiente paquete para llenar la capacidad restante.
5. Deténgase en cuanto la capacidad restante llegue a cero.

Nota de corrección: el original Java bucle avanzado i Solo cuando un paquete no cabía, lo que provocaba que se tomara el mismo paquete repetidamente. La versión anterior avanza un paquete por iteración y añade un paso de llenado fraccional, que coincide con la regla de la mochila fraccional.

Java Controlador que ejecuta el algoritmo en un ejemplo práctico:

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 Greedy Three

Primero defina el KnapsackPackage clase. La __lt__ Este método permite ordenarlo directamente por coste:

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

A continuación, implementa la rutina de la mochila fraccionaria:

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)

Función mochilaGreProc() en Python

Nota de corrección: el original Python La clase definió un vacío __init__ sin cuerpo, lo cual eleva IndentationErrorLa versión anterior elimina el constructor vacío porque no es necesario.

Controlador que ejecuta el algoritmo en 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)

C# Code para Greedy Three

Definir el KnapsackPackage clase:

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; } }
    }
}

Implementar Greedy Three con un paso de relleno fraccional:

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);
}

Función KnapsackGreProc() en C#

Contraejemplo: Tres codiciosos en mochila 0/1

Greedy Three es óptimo para la variante Fraccional, pero en la mochila 0/1 (donde los objetos no se pueden dividir) puede ser superado. Contraejemplo:

• Parámetros: n = 3, M = 10.
• Paquetes: {i = 1; W = 7; V = 9; coste = 9/7}, {i = 2; W = 6; V = 6; coste = 1}, {i = 3; W = 4; V = 4; coste = 1}.
• El algoritmo Greedy Three elige el paquete 1 para un valor total de 9, mientras que la elección óptima 0/1 (paquete 2, paquete 3) alcanza 10.

La lección: utilice Greedy Three solo cuando se permitan fracciones. Para la variante 0/1, utilice Programación dinámica .

Aplicaciones del modelo de la mochila fraccionada

• Carga de mercancías donde los productos líquidos, en polvo o a granel se pueden dividir por peso.
• Asignación de cartera entre opciones de inversión que aceptan financiación parcial.
• Compartición de ancho de banda en la nube, donde los flujos pueden consumir una fracción de un enlace.
• Planificación de la CPU bajo un modelo de división de tiempo compartida con cargas de trabajo divisibles.
• Asignación de recursos de IA donde una tarea de entrenamiento puede usar una fracción de una GPU.

Preguntas Frecuentes