Ramifica y Poda

[DCienfuegos]

Hola buenas,

Tengo un algoritmo al que le cargas una lista de canciones con una valoracion y una duracion y pides al usuario que te diga un numero de minutos y que el algoritmo lo que haga sea añadir a dos listas las mejores opciones en vase a la valoracion y el tiempo.

Lo tengo en backtracking hecho funcionando a la perfección pero al hacerlo ahora con Ramifica y Poda soy incapaz a que funcione.

Así a simple vista a alguien se le ocurre algo? Sera problema del heuristico?

Gracias.
PD. si alguien se ve super generoso y quiere ver el proyecto entero se lo envio

Código:

package alg32889855.p7;

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class NodoCancion extends Nodo{

	
	
	
	private static List <Cancion> A = new ArrayList <Cancion>();
	private static List <Cancion> B = new ArrayList <Cancion>();
	private Integer tiempo;
	private boolean[] cancionesUsadas;
	private static List<Cancion> cancionesLeidas=new ArrayList<Cancion>();
	
	public static  List<Cancion> canciones = new ArrayList<Cancion>();
	public NodoCancion(Nodo padre,Integer tiempo,List<Cancion>A,List<Cancion> B,List<Cancion>canciones,boolean[] cancionesUsadas,List<Cancion> cancionesLeidas){
		this.profundidad=padre.profundidad;
		this.idPadre=padre.hashCode();
		this.tiempo=tiempo;
		this.cancionesUsadas=cancionesUsadas;
		this.A=A;
		this.B=B;
		this.canciones=canciones;
		for(int i=0;i<3;i++){
			// 
			if(i==1 && (getDuracion(A) + canciones.get(profundidad).getDuracion()) < tiempo){
				A.add(canciones.get(profundidad));
				cancionesLeidas.add(canciones.get(profundidad));
				cancionesUsadas[profundidad]=true;
			}
			if(i==2 && (getDuracion(B) + canciones.get(profundidad).getDuracion()) < tiempo){
				B.add(canciones.get(profundidad));
				cancionesLeidas.add(canciones.get(profundidad));
				cancionesUsadas[profundidad]=true;
			}
		}
		calcularValorHeuristico();
		profundidad++;
	}
	public NodoCancion(List<Cancion>A,List<Cancion> B,List<Cancion>canciones,Integer tiempo){
		this.A=A;
		this.B=B;
		this.canciones=canciones;
		this.tiempo=tiempo;
		this.cancionesUsadas=new boolean[canciones.size()];
		profundidad++;
	}
	
	

	@Override
	public void calcularValorHeuristico() {
		// TODO Auto-generated method stub
		int value=0;
		for(int i=0;i<=profundidad;i++){
			if(cancionesUsadas[i]){
				value+=cancionesLeidas.get(i).getValoracion();
			}
		}
		valorHeuristico=value;
		
	}
	@Override
	public ArrayList<Nodo> expandir(){
		ArrayList<Nodo> hijos = new ArrayList<Nodo>();
		for(int i=0;i<canciones.size();i++){
			if(!cancionesUsadas[i]){
				hijos.add(new NodoCancion(this,tiempo,A,B,canciones,cancionesUsadas,cancionesLeidas));
			}
		}
		
		return hijos;
	}
		
	
	public int getPuntuacion (List <Cancion> canciones){
		
		int contador = 0;
		for (int i=0; i<canciones.size(); i++){
			contador+=canciones.get(i).getValoracion();
		}
		return contador;	
	}
	
	public int getDuracion (List <Cancion> canciones){
		
		int contador = 0;
		for (int i=0; i<canciones.size(); i++){
			contador+=canciones.get(i).getDuracion();
		}
		return contador;	
	}
	public void imprimir(List<Cancion> canciones){
		for(int i=0; i<canciones.size();i++){
			System.out.println(canciones.get(i));
		}
	}

	@Override
	public boolean solucion() {
		if(profundidad==canciones.size()){
		System.out.println("Lista 1:\n");
		imprimir(A);
		System.out.println("Lista 2:\n");
		imprimir(B);
		return true;
		}
		else{
			return false;
		}
	}
	@Override
	public int valorInicialPoda() {
		// TODO Auto-generated method stub
		Integer puntuacion=getPuntuacion(canciones);
		Integer tiempo=getDuracion(canciones);
		return puntuacion/tiempo;
	}
	

}