Java - problema suma subconjuntos

   
Vista:

problema suma subconjuntos

Publicado por toni (2 intervenciones) el 20/01/2008 16:12:41
hola,

para una asignatura tengo que realizar un programa que utilizando backtracking, dado un conjunto de entrada C, i un numero i, de todos los subconjuntos de C que la suma de sus elementos sea i

bien, pues yo he hecho esto, pero no me devuelve los resultados esperados (esto es, hay subconjuntos que no prueba) , la verdad es que ya me he hecho un completo lio, alguien le podría hechar un vistazo a ver si ve donde fallo?

private int[] conjuntoE;
private int[] caux;
private int n;
private int valorsuma;
private Stack conjuntoS;
private int p;
private int pe;
int indiceEntrada = 0;
int indiceReinicio = 1;

int[] c = {1, 2, 3, 4};
int i = 4;

public Busqueda(int[] c, int i) {
conjuntoE = c;
valorsuma = i;

n = c.length;
caux = new int[n];
conjuntoS = new Stack();
p = 0;
pe = 0;

}

public Boolean encontrar() {
//posibilidades probadas
p++;
if(p==(2^n-1)){ //han sido probadas todas
return true;
}
while(indiceEntrada<n){

conjuntoS.push(conjuntoE[indiceEntrada]);

System.out.print("conjunto actual: " + ver(conjuntoS) + " con ");
System.out.println("con indice: (" + indiceEntrada);
if (sumac(conjuntoS) == valorsuma) { /* CASO */

System.out.println("Subconjunto valido: " + ver(conjuntoS));

indiceEntrada++;

} else if (sumac(conjuntoS) > valorsuma) {

conjuntoS.pop();
indiceEntrada++;

}else{
indiceEntrada++;
}


return encontrar();
}
conjuntoS.pop();
indiceEntrada--;
if(conjuntoS.empty()){

indiceEntrada = indiceReinicio;
indiceReinicio++;
}
return encontrar();
}

y esto es lo que me muestra tras la ejecucion:

conjunto actual: 1 con con indice: (0
conjunto actual: 12 con con indice: (1
conjunto actual: 123 con con indice: (2
conjunto actual: 124 con con indice: (3
conjunto actual: 14 con con indice: (3
conjunto actual: 2 con con indice: (1
conjunto actual: 23 con con indice: (2
conjunto actual: 24 con con indice: (3
conjunto actual: 3 con con indice: (2
conjunto actual: 34 con con indice: (3

por ejemplo, se olvida del 13 y del 4 :S


bueno, muchas gracias de antemano!!
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder

RE:problema suma subconjuntos

Publicado por Pasquini Bruno (88 intervenciones) el 20/01/2008 17:49:47
gratis no :P
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

RE:problema suma subconjuntos

Publicado por toni (2 intervenciones) el 20/01/2008 21:30:21
ah, es así como va en este foro? no lo sabía.. entonces, disculpad..
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

problema suma subconjuntos

Publicado por xor and xordan.tom@gmail.com (1 intervención) el 15/01/2016 17:06:27
Solución a SSP mediante computación analogica en : https://pnpanalogo.wordpress.com/2016/01/14/22/
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar