The Blog

Algoritmo BackTracking - Problema de la Mochila

2017-07-11 05:25:00

Antes de empezar con BackTracking es recomendable que mires el video https://www.youtube.com/watch?v=vdVpRjO7g84 hasta el minuto 8:30 para entender correctamente como funciona BackTracking y el árbol resultante.

Enunciado:
Teniendo una mochila con una capacidad de "N" y un grupo de objetos que tienen dos atributos, por un lado el peso "P" y por otro lado el precio "V" teniendo estas tres variables: Implementar un algoritmo que devuelva el conjunto de objetos que deberias meter en la mochila, para obtener el mayor beneficio con una capacidad "N".

Resultado:
Este arbol representa con un 1 los elementos de la lista que hay que meter en la mochila(Elementos 0 y 1)

Test:

public class Test {

	public static List objetos = new ArrayList();
    public static void main(String[] args){

    	objetos.add(new ObjetoMochila(0,4,2));
    	objetos.add(new ObjetoMochila(1,4,2));
    	objetos.add(new ObjetoMochila(2,9,7));

    	System.out.println("Solución: "+new BackTracking().recursividad(0,0,new ArrayList(),
    																	objetos,new ArrayList(),7));
    }
}

BackTracking:
public class BackTracking {

	public List recursividad(Integer indice,Integer peso,List lista,//Propiedades individual
											List objetos,List resultado,Integer capacidad){//Propiedades compartidas

		System.out.println(indice+" : "+peso+" -> "+lista); //Ver todo el arbol
    	if(indice == objetos.size() || peso == capacidad){

    		if(resultado.size() == 0 || lista.stream().mapToInt(x->x.getPrecio()).sum() > resultado.stream().mapToInt(x->x.getPrecio()).sum()){
    			resultado.clear();
    			resultado.addAll(lista);
    		}
 
    	}else{

			for(Boolean a : getAlternativa(indice,peso,objetos,lista,capacidad)){ //Las alternativas
				if(a == true){
					peso += objetos.get(indice).getPeso();
					lista.add(objetos.get(indice));
				}
					recursividad(indice+1,peso,lista,objetos,resultado,capacidad);
				if(a == true){
					peso -= objetos.get(indice).getPeso();
					lista.remove(objetos.get(indice));
				}
			}

    	}
        return resultado;
    }
    
    private List getAlternativa(Integer indice,Integer peso,List objetos,List lista,Integer capacidad){
    	List res = new ArrayList();
	    if((peso+objetos.get(indice).getPeso()) <= capacidad){
	    		res.add(true);
    	}
	    res.add(false);
    	return res;
    }

}

ObjetoMochila:
public class ObjetoMochila{

	private Integer codigo;
	private Integer precio;
	private Integer peso;
	
	ObjetoMochila(Integer codigo,Integer precio, Integer peso){
		this.codigo = codigo;
		this.precio = precio;
		this.peso = peso;
	}	

	public Integer getPeso() {
		return peso;
	}
	public Integer getPrecio() {
		return precio;
	}
	public Integer getCodigo() {
		return codigo;
	}
	
	@Override
	public String toString() {
		return "<"+codigo+", Precio "+precio+", Peso "+peso+">";
	}
	
}

Comments (1)

Leave a comment

Su mensaje ha sido enviado correctamente. ¡Muchas gracias!. Recuerda reiniciar la pagina para ver el comentario.

No ha sido posible enviar el mensaje. Revise los datos