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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
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:
|
1 |
public static void llenarMochila(Mochila m_base, Elemento[] elementos, boolean llena, Mochila m_opt) |
Este seria la función completa.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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.
buenas me gustaria contactarte para que me podes ayudar
me gustaria contactarte para que podres explicar porfa