El problema de la mochila en Java con backtracking

Hola a todos, hoy os voy a explicar como resolver el problema de la mochila con backtracking.

El problema de la mochila es un problema muy común de backtracking.

Básicamente, consiste en lo siguiente: tenemos una mochila con un tamaño máximo que nosotros le indicamos, también tenemos varios elementos que tienen un peso y un valor o beneficio.

El objetivo del programa es sacar la mejor combinación con mayor beneficio siempre y cuando no supere el peso de la mochila.

Se puede hacer de varias formas, pero en este caso, lo haremos con backtracking para encontrar la mejor combinación de beneficio.

¿Por donde empezamos? Lo primero que debemos pensar es que vamos a necesitar para hacer esa función recursiva y que clases podríamos crear.

En este caso, lo mejor es hacer una clase mochila para almacenar los elementos y poder mostrarlos después. Tambien necesitaremos hacer una clase simple llamada Elemento.

— Elemento


public class Elemento {
 
    private int peso;
    private int beneficio;

    public Elemento(int peso, int beneficio) {
        this.peso = peso;
        this.beneficio = beneficio;
    }

    public int getPeso() {
        return peso;
    }

    public void setPeso(int peso) {
        this.peso = peso;
    }

    public int getBeneficio() {
        return beneficio;
    }

    public void setBeneficio(int beneficio) {
        this.beneficio = beneficio;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final Elemento other = (Elemento) obj;
        if (this.peso != other.peso) {
            return false;
        }
        if (this.beneficio != other.beneficio) {
            return false;
        }
        return true;
    }

    @Override
    public String toString(){
        return "Peso:"+peso+","+" beneficio:"+beneficio;
    }
    
    
}

— Mochila


public class Mochila {

    private int pesoMaximo;
    private Elemento[] elementos;

    private int peso;
    private int beneficio;

    public Mochila(int pesoMaximo, int numElementos) {
        this.pesoMaximo = pesoMaximo;
        this.elementos = new Elemento[numElementos];
        this.beneficio = 0;
        this.peso = 0;
    }

    public Elemento[] getElementos() {
        return elementos;
    }

     public int getPeso() {
       return peso;
    }
    
    public void setPeso(int peso) {
        this.peso = peso;
    }

    public int getBeneficio() {
        return beneficio;
    }

    public void setBeneficio(int beneficio) {
        this.beneficio = beneficio;
    }

    public int getPesoMaximo() {
        return pesoMaximo;
    }

    public void setPesoMaximo(int pesoMaximo) {
        this.pesoMaximo = pesoMaximo;
    }

    /**
     * Añade un elemento a la mochila
     * @param e 
     */
    public void aniadirElemento(Elemento e) {

        for (int i = 0; i < this.elementos.length; i++) {
            if (this.elementos[i] == null) {
                this.elementos[i] = e; //lo añade
                this.beneficio+=e.getBeneficio(); // aumenta el beneficio
                this.peso+=e.getPeso(); // Aumenta el piso
                break;
            }
        }

    }

    /**
     * Vaciamos la mochila
     */
    public void clear() {
        this.peso=0;
        this.beneficio=0;
        for (int i = 0; i < this.elementos.length; i++) {
            this.elementos[i] = null;
        }
    }

    /**
     * Elimina elemento dado
     * @param e 
     */
    public void eliminarElemento(Elemento e) {
        for (int i = 0; i < this.elementos.length; i++) {
            if (this.elementos[i].equals(e)) {
                this.elementos[i] = null; //el elemento fuera
                this.peso-=e.getPeso(); //Reduce el peso
                this.beneficio-=e.getBeneficio(); // reduce el beneficio
                break;
            }
        }
    }
    
    /**
     * Indica si existe un elemento
     * @param e
     * @return 
     */
    public boolean existeElemento(Elemento e) {
        for (int i = 0; i < this.elementos.length; i++) {
            if (this.elementos[i] != null && this.elementos[i].equals(e)) {
                return true;
            }
        }
        return false;
    }

    /**
     * Muestra la mochila
     * @return 
     */
    public String toString() {
        String cadena="";
        for (int i = 0; i < this.elementos.length; i++) {
            if (this.elementos[i] != null) {
                cadena+=elementos[i]+"\n";
            }
        }
        cadena+="Peso: " + getPeso()+"\n";
        cadena+="Beneficio: " + getBeneficio()+"\n";
        return cadena;
    }

}

Ya tenemos la mochila y los elementos.

Para llamar a la función recursiva, necesitaremos una mochila donde vayamos metiendo elementos y otra donde almacenaremos la mejor combinación.

También necesitaremos los elementos sueltos (en un array).

Otra cosa que también necesitaremos es saber cuando debemos comprobar si nuestra mochila es mejor que la que ya tenemos, podemos usar un booleano para ello.

Este seria la definición de la función:


public static void llenarMochila(Mochila m_base, Elemento[] elementos, boolean llena, Mochila m_opt)

Este seria la función completa.

  public static void llenarMochila(Mochila m_base, Elemento[] elementos, boolean llena, Mochila m_opt) {

        //si esta llena
        if (llena) {
            //compruebo si tiene mas beneficio que otra
            if (m_base.getBeneficio() > m_opt.getBeneficio()) {

                Elemento[] elementosMochBase = m_base.getElementos();
                m_opt.clear();

                //metemos los elementos
                for (Elemento e : elementosMochBase) {
                    if (e != null) {
                        m_opt.aniadirElemento(e);
                    }

                }

            }

        } else {
            //Recorre los elementos
            for (int i = 0; i < elementos.length; i++) {
                //si existe el elemento
                if (!m_base.existeElemento(elementos[i])) {
                    //Si el peso de la mochila se supera, indicamos que esta llena
                    if (m_base.getPesoMaximo() > m_base.getPeso() + elementos[i].getPeso()) {
                        m_base.aniadirElemento(elementos[i]); //añadimos
                        llenarMochila(m_base, elementos, false, m_opt);
                        m_base.eliminarElemento(elementos[i]); // lo eliminamos
                    } else {
                        llenarMochila(m_base, elementos, true, m_opt);
                    }

                }

            }

        }

    }

Os dejo tambien como llamamos a la función:


public static void main(String[] args) {

        Elemento[] elementos = {
            new Elemento(1, 1),
            new Elemento(2, 2),
            new Elemento(4, 10),
            new Elemento(1, 2),
            new Elemento(12, 15)
        };

        Mochila m_base = new Mochila(15, elementos.length);
        Mochila m_opt = new Mochila(15, elementos.length);

        llenarMochila(m_base, elementos, false, m_opt);

        System.out.println(m_opt);
    }

Por ultimo un vídeo donde lo explico todo, en la descripción esta el ejercicio completo para descargar:

Espero que os sea de ayuda.Si tenéis dudas, preguntad. Estamos para ayudarte.

¿Te ha gustado y quieres apoyarme? ¡Sé mi patrón!
Etiquetas

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *