Run Backtracking algorithm

3

First of all, during all this time ago I have been using this model to solve my problems with backtracking.

``````        private void bt() {
actualizaSoluciones();
if(AlgoritmoBT.soloLaPrimeraSolucion  && solucion!=null) exito = true;
if(!AlgoritmoBT.soloLaPrimeraSolucion  && soluciones.size()>=AlgoritmoBT.numeroDeSoluciones) exito = true;
} else {
bt();
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){

BackTraking a = new BackTraking();
}
}
``````

BackTraking:

``````    import java.util.ArrayList;
import java.util.List;

public class BackTracking {

List<Objeto> res = new ArrayList<Objeto>();

if(indice == Test.lista.size()-1){
}else{
for(Objeto a : getAlternativas(res)){

}
}

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){
}
}
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).

source

3

``````public List<Objeto> recursividad(Integer indice){
if(indice == Test.lista.size()-1){
``````

If the index is less than the test size. list for all cases except the last

`````` res.add(Test.lista.get(indice));
``````

I add the object to res, which will be lost when it comes out because it is local

``````}else{
``````

If it's not the last one on the list ... I do not know why the last one is always added ... that's weird

``````for(Objeto a : getAlternativas(res)){
``````

In theory you are comparing the values, however your set of tests has no one to pass ...

``````res.add(a);
``````

Do you add all the objects that are cheaper than your budget ... and the votes where you look at them?

``````recursividad(indice+1);
}
}

return res;
}
``````

What I see in all this is the following .. I do not understand how you can calculate what you want backtracking, there is no backtracking here, it is a simple search of lesser value. Suppose you can by backtracking, your algorithm should try paths (to go and return, I do not see them here) and compare the two things you need ..

I think this is not the problem to learn backtracking, and your algorithm is missing many things.