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!!
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
0