I have been trying to do the backpack problem through backtracking. I've got it, the problem is that I can not get the most optimal solution.
public List<ObjetoMochila> recursividad(Integer indice,Integer peso,List<ObjetoMochila> lista,List<ObjetoMochila> objetos,List<ObjetoMochila> resultado,Integer capacidad){//Propiedades compartidas
//Estado final = he recorrido todo el grafo o cuando peso = capacidad
if(indice == objetos.size() || peso == capacidad){
//Guardo la solución mas optima, comparo los precios
if(resultado.size() == 0 || lista.stream().mapToInt(x->x.getPrecio()).sum() > resultado.stream().mapToInt(x->x.getPrecio()).sum()){
resultado.clear();
resultado.addAll(lista);
}
}else{
//Si peso(total) + peso(actual) <= capacidad, lo añado
if((peso+objetos.get(indice).getPeso()) <= capacidad){
peso += objetos.get(indice).getPeso();
lista.add(objetos.get(indice));
}
//Proximo estado
recursividad(indice+1,peso,lista,objetos,resultado,capacidad);
}
return resultado;
}
Any solution?