Jordi
02 de Agosto del 2004

Hola a todos!

Simplemente, tengo un vector con 5 elementos, i me suma los que en contienen valor 1 en otro vector, es decir:

a[5] = {1,2,3,4,5}
b[5] = {1,0,0,1,0}

Me sumara 1 mas 4.

El problema es que tengo que hacer en backtraking, io poner X numeros, y saber si pueden sumar Y.

Lo he probado horas y horas, sin resultado, el codigo del backtracking aqui viene (el que e intentado yo)

while(!trobat && pos < 5) {
solucio[pos] = 1;
sumar(numeros,solucio,suma_total,trobat);
if(trobat) { cout << "S'ha trobat la suma" << endl; }
buscar(numeros,solucio,suma_total,trobat,pos+1);
if(!trobat) {
solucio[pos] = 0;
}
pos++;
}
}

Creo que el error puede venir al intentar poner a 0 otra vez el solucio[pos] que no me sume Y.

Numeros = array con los numeros
Solucio = array con los 1,0,0,1.... etc
Trobat = boleano que dice si lo a encontrado
suma_total = la suma que tiene que sumar

juanin
02 de Agosto del 2004

Hola. Bueno, el codigo que mandas no lo veo demasiado claro. Para empezar, ¿que es buscar? Segundo, el codigo este ¿es una funcion? He pensado que quiza sea la misma cosa y que intentas hacerlo de forma recursiva, pero te faltaria la condicion de parada. Ademas es bastante ineficiente (orden exponencial con el numero de elementos del vector)
Mi idea es que empieces por el numero mayor. Si los tienes ordenados de menor a mayor pues empiezas por el ultimo. Tambien necesitas conocer para cada intento, no solo si es el numero que buscas, sino si es mayor o menor (modifica la funcion sumar). Despues, con el mismo bucle que tienes:

pos = 4;
trobat = 0;
while(!trobat && pos >= 0) {
solucio[pos] = 1;
sumar(numeros,solucio,suma_total,trobat, mayor);
if(trobat) { cout << "S'ha trobat la suma" << endl; }
else{
if(!mayor)
solucio[pos] = 0;
pos --;
}
}