Backtracking | Backpack

0

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?

    
asked by 09.10.2017 в 18:42
source

0 answers