Antes que nada, durante todo este tiempo atrás he estado usando este modelo para resolver mis problemas con backtracking.
Es un modelo de backtraking realizado por mi universidad https://github.com/migueltoro/apuntesjava/blob/master/SoftwareDelLibro/src/us/lsi/bt/AlgoritmoBT.java.
private void bt() {
if(estado.isFinal()){
actualizaSoluciones();
if(AlgoritmoBT.soloLaPrimeraSolucion && solucion!=null) exito = true;
if(!AlgoritmoBT.soloLaPrimeraSolucion && soluciones.size()>=AlgoritmoBT.numeroDeSoluciones) exito = true;
} else {
for(A a: filtraRandomize(estado,estado.getAlternativas())){
if(isMin() && estado.getObjetivoEstimado(a) >= mejorValor) continue;
if(isMax() && estado.getObjetivoEstimado(a) <= mejorValor) continue;
estado.avanza(a);
bt();
estado.retrocede(a);
if (exito) break;
}
}
}
Ejemplo: Como resolver el problema de las reinas con el modelo mencionado anteriormente https://github.com/migueltoro/apuntesjava/blob/master/SoftwareDelLibro/src/us/lsi/bt/reinas/EstadoReinasBT.java
Una vez leído lo anterior, comienzo con mi duda. Estoy intentando deshacerme del modelo mencionado anteriormente para realizar mis problemas mediante backtraking, he estado intentando realizar el siguiente problema:
Tengo una lista con todos los grupos(de cantantes(Test.lista)) que puedo seleccionar, tengo 9.0€ de presupuesto para contratar los grupos con el mayor numero de votos (Maximizar votos).
Tengo bastante código realizado de lo que quiero conseguir:
Grupos:
public class Objeto{
private Integer codigo;
private String nombre;
private Integer votos;
private Double precio;
private Boolean cerca;
public Objeto(Integer codigo, String nombre, Integer votos, Double precio, Boolean cerca) {
this.codigo = codigo;
this.nombre = nombre;
this.votos = votos;
this.precio = precio;
this.cerca = cerca;
}
public Integer getCodigo() {
return codigo;
}
public String getNombre() {
return nombre;
}
public Integer getVotos() {
return votos;
}
public Double getPrecio() {
return precio;
}
public Boolean getCerca() {
return cerca;
}
@Override
public String toString() {
return "Objeto [codigo=" + codigo + ", nombre=" + nombre + ", votos=" + votos + ", precio=" + precio
+ ", cerca=" + cerca + "]";
}
}
Test:
import java.util.ArrayList;
import java.util.List;
public class Test {
public static List<Objeto> lista = new ArrayList<Objeto>();
public static Double presupuesto = 9.0;
public static void main(String[] args){
lista.add(new Objeto(1,"Caracola1",100,9.0,true));
lista.add(new Objeto(2,"Caracola2",2,4.0,true));
lista.add(new Objeto(3,"Caracola3",3,5.0,false));
BackTraking a = new BackTraking();
System.out.println(a.recursividad(0));
}
}
BackTraking:
import java.util.ArrayList;
import java.util.List;
public class BackTracking {
public List<Objeto> recursividad(Integer indice){
List<Objeto> res = new ArrayList<Objeto>();
if(indice == Test.lista.size()-1){
res.add(Test.lista.get(indice));
}else{
for(Objeto a : getAlternativas(res)){
res.add(a);
recursividad(indice+1);
}
}
return res;
}
public List<Objeto> getAlternativas(List<Objeto> lista) {//Todos los objetos que no sobrepasen el presupuesto y no esten en la lista
List<Objeto> res = new ArrayList<Objeto>();
Double coste = lista.stream().mapToDouble(x->x.getPrecio()).sum();
for(Objeto a : Test.lista){
if(!lista.contains(a) && (coste+a.getPrecio()) <= Test.presupuesto){
res.add(a);
}
}
return res;
}
}
Solución obtenida :(
[
Objeto [codigo=2, nombre=Caracola2, votos=2, precio=4.0, cerca=true]
,
Objeto [codigo=3, nombre=Caracola3, votos=3, precio=5.0, cerca=false]
,
Objeto [codigo=1, nombre=Caracola1, votos=100, precio=9.0, cerca=true]
]
Solución que tendría que salir :)
El resultado obtenido tendría que ser new Objeto(1,"Caracola1",100,9.0,true)
puesto que cumple que tiene 9.0€ de precio y el que mayor numero de votos tiene (100).