Problema de la mochila

El problema de la mochila es un problema típico de programación entera que responde a la siguiente situación: imagínese que un ladrón entra a un almacén para substraer una serie de elementos con una única mochila que tiene una capacidad limitada en cuanto al peso que puede contener. Cada objeto que se introduce carga la mochila con más peso, pero a su vez representa un beneficio económico por el valor del mismo. El problema surge cuando se debe elegir qué objetos seleccionar para llevar en la mochila de forma que el beneficio sea máximo.

Esta situación se presenta con cierta frecuencia en los ámbitos económico e industrial, donde la mochila suele representar la restricción presupuestaria (cantidad máxima de recursos económicos de los que se dispone) y donde la utilidad de los objetos seleccionados se equipara a un beneficio económico por adquirir o llevar a cabo ciertas acciones.

Para modelar este problema se utilizará una clase denominada Elemento que contendrá solamente la descripción de cada elemento, su peso y su valor, así:

class Elemento {
    String nombre;
    double valor;
    double peso;
    Elemento(String n, double v, double p) {
        nombre=n;
        valor =v;
        peso  =p;
    }
    public String toString() {
        return String.format("%-15s %,12.2f %,12.2f", nombre, valor, peso);
    }
}

La modelación termina con una clase denominada ProblemaMochila en la que se crearán dos vectores para simular el almacén, es decir, los elementos disponibles, y la mochila, dónde se ubicarán los elementos a ser substraídos. Se tienen métodos adicionales para mostrar el contenido de la mochila, así como para llenar el almacén con los elementos iniciales:

import java.util.*;

public class ProblemaMochila {
    Vector<Elemento> almacen = new Vector<Elemento>();
    Vector<Elemento> mochila = new Vector<Elemento>();
    final double  pesoMaximo;

    public ProblemaMochila(int pm) {
        pesoMaximo = pm;
        cargarDatos();
    }

    public void cargarDatos() {
        almacen.add(new Elemento("TV",        300, 15));
        almacen.add(new Elemento("PS3",       100,  3));
        almacen.add(new Elemento("Libro Java", 10,  1));
        almacen.add(new Elemento("DVD Player",  5,  0.5));
        almacen.add(new Elemento("Blu-Ray",    50,  0.5));
        almacen.add(new Elemento("Balon",      30,  0.5));
        almacen.add(new Elemento("iPod",      150,  1));
        almacen.add(new Elemento("Printer",    20,  4));
        almacen.add(new Elemento("VideoBeam", 200,  4));
        almacen.add(new Elemento("LapTop",     20,  3));
        almacen.add(new Elemento("iPad",      150,  2));
        almacen.add(new Elemento("PC",        100,  5));
        almacen.add(new Elemento("BlackBerry",150,  0.5));
   }

     public void mostrarMochila() {
        double pesoMochila=0;
        double valorMochila=0;
        System.out.println();
        for(Elemento e: mochila) {
            System.out.println(e);
            pesoMochila+=e.peso;
            valorMochila+=e.valor;
        }
        System.out.println("------");
        System.out.printf("Peso  = %,12.2f %n", pesoMochila);
        System.out.printf("Valor = %,12.2f %n", valorMochila);
    }

    public static void main(String[] args) {
        // Crear una mochila que soporta hasta 20 Kg. de peso
        ProblemaMochila pm = new ProblemaMochila(20);
        pm.resolverProblema();
        pm.mostrarMochila();
    }
}

Para resolver el problema existen varias estrategias, entre las cuales pueden estar la de ir llenando la mochila con los elementos más costosos, o con los elementos menos pesados. En el caso de llenar la mochila con los elementos más costosos primero, el método resolverProblema se plantearía así:

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 - y.valor);
            }
        };
        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++;
        }
    }

Si se quiere ordenar usar otra estrategia, como la de ir llenando la mochila en primer lugar con los elementos más livianos, bastaría cambiar el comparador cmp para que reste pesos en lugar de valores

Proximamente se publicarán otros enfoques para resolver este problema.