The Blog

Algoritmo BackTracking - Problema del Festival

2017-07-10 00:00:00

Backtracking es una manera de recorrer un arbol de posibles soluciones. Imagina que quieres cruzar un laberinto, el laberinto tiene una puerta de entrada y salida.

Estas frente a la puerta de entrada y tienes tres caminos a seguir, escoges el de la derecha y marcas con una raya en la pared antes de entrar en ese camino, caminas y te topas con otras division, nuevamente tres caminos, escoges el de la derecha y lo marcas (en la pared con una raya de tiza), te vas por el camino y te encuentras que esta cerrado..
¿Que haces? pues te devuelves (back) y vuelves a la ultima division ahora tienes solo dos caminos para escoger, escoges el de mas a la derecha y que no esta marcado, lo marcas, y avanzas, cerrado, te devuelves a la division, escoges el de mas a la derecha que no este marcado (igual queda uno) lo marcas, avanzas, cerrado, te devuelves, y.. no queda nada para escoger, todo esta marcado, te devuelves y vuelves a la primera division, y escoges el camino mas a la derecha que no este marcado...

Funcionamiento BackTracking:


Enunciado:


Test:

public class Test {

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

    	objetos.add(new Grupo("Corizonas",9,4000.0,"viernes","tarde",false,true));
    	objetos.add(new Grupo("RussianRed",6,3000.0,"viernes","tarde",false,false));
    	objetos.add(new Grupo("Sidonie",5,5000.0,"viernes","tarde",false,true));
    	objetos.add(new Grupo("LoveOfLesbian",12,5000.0,"viernes","noche",true,false));
    	objetos.add(new Grupo("Dorian",5,2000.0,"viernes","noche",false,false));
    	objetos.add(new Grupo("Niños Mutantes",3,3000.0,"viernes","noche",true,true));
    	objetos.add(new Grupo("IZAL",8,6000.0,"sabado","tarde",false,false));
    	objetos.add(new Grupo("LA",6,3000.0,"sabado","tarde",false,false));
    	objetos.add(new Grupo("León Benavente",6,4000.0,"sabado","tarde",false,false));
    	objetos.add(new Grupo("ArizonaBaby",8,3000.0,"sabado","noche",true,false));
    	objetos.add(new Grupo("Igloo",6,1000.0,"sabado","noche",false,true));
    	objetos.add(new Grupo("Grises",6,2000.0,"sabado","noche",true,true));

        List lista2 = new BackTracking().recursividad(0,objetos,
        													new ArrayList(),new ArrayList(),10000.0);
        System.out.println(lista2);
    }
}

BackTracking:
public class BackTracking {

    public List recursividad(Integer indice,List objeto, //Propiedades individual
    								List lista,List resultado,Double presupuestoRestante){ //Propiedades compartidas

    	if((indice == objeto.size() || presupuestoRestante == 0) && getSegundo(lista) >= 2 && getPrimero(lista) <= 2 && getTercero(lista) == true){ //Cuando haya recorrido toda la lista o haya gastado todo el presupuesto

    			//Obtengo la lista con mayor numero de votos
    			if(resultado.size() == 0 || lista.stream().mapToDouble(x->x.getVotos()).sum() > resultado.stream().mapToDouble(x->x.getVotos()).sum()){
	        		resultado.clear(); //Elimino la lista que hubiese antes
	        		resultado.addAll(lista); //Añado la nueva lista
	        	}
 
	        }else{
	        	for(Grupo a : getAlternativa(objeto,indice,presupuestoRestante)){ //Las alternativas

        			presupuestoRestante-=a.getPrecio(); //Añado
	        		lista.add(a);
        		
	        	    recursividad(indice+1,objeto,lista,resultado,presupuestoRestante);
	        	
	        		presupuestoRestante+=a.getPrecio(); //Elimino
	        		lista.remove(a);
        	}
        }
        return resultado;

    }
    
    public List getAlternativa(List objeto,Integer indice,Double presupuestoRestante){
		List res = new ArrayList();
		for(Grupo a : objeto){
			if((a.getPrecio() <= presupuestoRestante)){
				res.add(a);
			}
		}
		return res;
    }
    
	private Boolean getTercero(List lista1) { //No mas de una actuacion por dia
		int a = 0;
		int b = 0;
		int c = 0;
		int d = 0;
	
		for(Grupo lista : lista1){
			if(lista.getDia().equals("viernes") && lista.getHora().equals("tarde")){
				a++;
		    }
			if(lista.getDia().equals("viernes") && lista.getHora().equals("noche")){
				b++;
		    }
			if(lista.getDia().equals("sabado") && lista.getHora().equals("tarde")){
				c++;
		    }
			if(lista.getDia().equals("sabado") && lista.getHora().equals("noche")){
				d++;
		    }
		}
		return a==1&&b==1&&c==1&&d==1;
	}
	
	private Long getPrimero(List lista) { //2 grupo deben haber estado cerca
		return lista.stream().filter(x -> x.esCerca() == true).count();
	}
	private Long getSegundo(List lista) { //2 grupo deben haber sido nuevo
		return lista.stream().filter(x -> x.esNuevo() == true).count();
	}

}

Grupo:
public class Grupo{

	private String nombre;
	private Integer votos;
	private Double precio;
	private String dia;
	private String hora;
	private boolean cerca;
	private boolean nuevo;
	
	public Grupo(String nombre, Integer votos, Double precio,
			String dia, String hora, boolean cerca, boolean nuevo) {
		super();
		this.nombre = nombre;
		this.votos = votos;
		this.precio = precio;
		this.dia = dia;
		this.hora = hora;
		this.cerca = cerca;
		this.nuevo = nuevo;
	}
	
	public String getNombre() {
		return nombre;
	}
	
	public Integer getVotos() {
		return votos;
	}
	
	public Double getPrecio() {
		return precio;
	}
	
	public String getDia() {
		return dia;
	}
	
	public String getHora() {
		return hora;
	}

	public boolean esCerca() {
		return cerca;
	}
	
	public boolean esNuevo() {
		return nuevo;
	}

	@Override
	public String toString() {
		return nombre;
	}

}

Comments (4)

  • <a href="http://payday1000loans3000online.com">quick loans </a> http://payday1000loans3000online.com - loans online &lt;a href=&quot;http://payday1000loans3000online

  • topoo56c8y</br> male enhancement reviews</br> <a href="http://malesenhancement.com"> male enhancement exercises</a> </br> &lt;a href=&quot;http://

  • payday installment loans <a href="http://cashadvances2017.com"> payday loans direct lender</a> &lt;a href=&quot;http://cashadvances2017.com&quot;&gt; best payday

  • payday loans online direct lenders <a href="http://paydayloans2017.com"> payday loans online no credit check</a> &lt;a href=&quot;http://paydayloans2017.com&quot;&

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