Problema de la mochila - Backtracking

Resolver el problema de la mochila seleccionando los elementos más caros en primer lugar, o los más livianos, no necesariamente garantiza llegar a una solución ideal, pues es posible que otras combinaciones de elementos produzcan mejores resultados.

Para obtener la solución ideal se deben revisar todas las alternativas; y en este caso, se puede utilizar una estrategia de retroceso, o backtracking. En esta implementación, iniciando en el primer elemento del almacén, se evalúan dos posibilidades, agregar o no agregar el elemento a la mochila, y llamando recursivamente el método hasta que la mochila se llena; una vez llena, se compara con el máximo calculado anteriormente y se guarda la lista de elementos que genere el mayor valor en la mochila. Esta solución requiere una mochila temporal (tmpMochila) que se crea en forma similar a la mochila definitiva, y dos métodos que calculen el valor y el peso acumulado de dicha mochila temporal. La implementación queda entonces de la siguiente manera:

// Solución por backtracking
    public void resolverProblemaBT(int posicion) {
        double  pesoMochila=getPeso(tmpMochila);    // peso de la solucion temporal
        double valorMochila=getValor(tmpMochila);   // valor de la solucion temporal

        if( posicion>=almacen.size() ) {            // si ya se tuvieron en cuenta todos los elementos
            if(valorMochila>valorMaximo) {          // si el valor es mayor que el máximo anterior
                valorMaximo=valorMochila;           // se actualiza el valor mayor
                mochila.clear();
                mochila.addAll(tmpMochila);
            }
            return;
        }
        Elemento e = almacen.get(posicion);
        // Si el elemento se puede agregar, se envía a la mochila temporal
        if(pesoMochila + e.peso <= pesoMaximo) {
                tmpMochila.add(e);                  // Se agrega a la mochila temporal
                resolverProblemaBT(posicion+1);     // se revisa para el siguiente elemento
                tmpMochila.remove(e);               // Se retira el elemento
        }
        // Si no se pudo agregar, o ya se agregó y se retiró, se revisa para el siguiente
        resolverProblemaBT(posicion+1);
    }

    double getPeso(List<Elemento> tmp) {
        double respuesta=0;
        for(Elemento e: tmp) respuesta+=e.peso;
        return respuesta;
    }

    double getValor(List<Elemento> tmp) {
        double respuesta=0;
        for(Elemento e: tmp) respuesta+=e.valor;
        return respuesta;
    }

El método de invocación quedaría de la siguiente manera (no olvidar crear el vector tmpMochila como un Vector de objetos de tipo Elemento):

    public static void main(String[] args) {
        ProblemaMochila pm = new ProblemaMochila(20);
        pm.resolverProblemaBT(0);       // Inicia en el primer elemento disponible
        pm.mostrarMochila();
    }

Este método devuelve la solución óptima, puesto que evalúa todas las posibilidades, sin embargo, cuando el número de elementos disponibles es relativamente grande, la cantidad de operaciones a realizar hace prácticamente imposible utilizar el algoritmo, ya que su complejidad es del orden de O(N!), donde N es la cantidad de elementos del almacén.