Problema de la mochila - Algoritmos Voraces

Si bien la solución por backtracking permite obtener la mejor solución al problema de la mochila, existe el problema de que cuando la cantidad de elementos a evaluar es relativamente grande, los tiempos de respuesta se vuelven prohibitivos. Por otro lado, la solución de agregar primero los elementos más costosos, o lo más livianos, no garantiza una solución óptima, o por lo menos parecida a la óptima.

Estas dos aproximaciones representan el concepto de algoritmos voraces, donde se selecciona una estrategia que permite decidir si un elemento se agrega o no a la solución. En los casos mencionados se utilizaba la estrategia del mayor costo o la del menor peso. Una mejor solución se presenta cuando se utiliza el costo por unidad de peso para ordenar los elementos, de esta manera, un elemento muy caro no se agrega si pesa demasiado en comparación con otro de menor valor, pero de mucho menor peso. La función resolverProblema queda entonces de la siguiente manera:

    public void resolverProblema() {
        // Comparador para ordenar los elementos del almacen por valor
        Comparator cmp = new Comparator<Elemento>() {
            public int compare(Elemento x, Elemento y) {
                return (int) (x.valor/x.peso - y.valor/y.peso);
            }
        };
        Collections.sort(almacen,cmp);  // ordena usando el comparador anterior
        Collections.reverse(almacen);   // reversa el orden de los elementos

        double pesoMochila=0;
        int    posicion=0;
        while(pesoMochila<pesoMaximo && posicion < almacen.size()) {
            Elemento tmp = almacen.get(posicion);
            if(pesoMochila + tmp.peso <= pesoMaximo) {
                mochila.add(tmp);
                pesoMochila+=tmp.peso;
            }
            posicion++;
        }
    }

En cuanto al desempeño de este método, su complejidad es la equivalente al proceso de ordenación de la lista de elementos por su valor por unidad de peso, que es O(N log N), ya que el proceso de llenado de la mochila es lineal.

En el caso de ejemplo, este método da una respuesta con un peso total de 18 Kg y un costo de $945, mientras que la respuesta obtenida por backtracking es de 20 Kg con un costo de $955, lo que muestras que se obtiene un valor muy cercano al óptimo en una fracción del tiempo.