First of all, during all this time ago I have been using this model to solve my problems with backtracking.
It's a backtraking model made by my university link .
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;
}
}
}
Example: How to solve the queens problem with the model mentioned above link
Once I have read the above, I begin with my doubt. I'm trying to get rid of the model mentioned above to make my problems through backtraking, I've been trying to do the following problem:
I have a list with all the groups (of singers (Test.list)) that I can select, I have 9.0 € of budget to contract the groups with the highest number of votes (Maximize votes).
I have enough code made of what I want to achieve:
Groups:
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;
}
}
Solution obtained: (
[
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]
]
Solution that would have to leave:)
The result obtained would have to be new Objeto(1,"Caracola1",100,9.0,true)
since it fulfills that it has 9.0 € of price and the one that greater number of votes has (100).