Suma de Conjuntos con Vuelta Atrás (Backtracking) en C

[maritere22]

Buenas tardes.
Tengo que implementar en lenguaje C un programa que haga lo siguiente:

Dado un conjunto de N números enteros positivos ordenados de menor a mayor y un número S también entero positivo, dar el número de subconjuntos cuya suma sea S, usando la técnica de Vuelta Atrás (Backtracking).

Le estoy dando muchas vueltas y no consigo dar con la solución, también he buscado por internet y he encontrado muchas soluciones, pero están en C++, Pascal, etc. y no sé pasar de un lenguaje a otro.

Por favor, ¿alguien podría implementar este programa por mi y darme el código, de la forma más sencilla posible?
Se lo agradecería muchísimo...

[0xDani]

Lo primero: hay un subforo específico dedicado a la programación en C/C++.

Lo segundo, te has informado sobre dicha técnica y/o has hecho algún intento antes de venir a pedir que te hagan el código?

Saludos.

[maritere22]

Perdona, no sabía que había un subforo.
Lo de haber hecho pruebas ya lo he puesto en la explicación de mi problema. He estado haciendo pruebas y no lo he podido conseguir, por eso acudo al foro.
Saludos a ti también.

[0xDani]

Pues pon códigos de intentos que hayas hecho, para que podamos ver los fallos y ayudarte a corregir, pero no lo pidas hecho. Si no pones nada de tu parte lo más probable es que nadie te ayude.

[maritere22]

De acuerdo. Aquí está lo que he hecho hasta ahora. Obviamente, está mal, seguro que es una catástrofe.
He ido añadiendo y quitando cosas y ya no sé por donde cogerlo.
Como está tan mal, por eso pedía el código, no creo que el mío tenga arreglo fácil...

Código [Seleccionar] Expandir


#include <stdio.h>
#include <math.h>
#define length(x) (sizeof(x)/sizeof(x[0]))


static int V[]={1,2,3,4},aux[]={0,0,0,0},ex[]={}; //ex: vector que contiene al ultimo elemento expandido
//aux: deberia contener los elementos del subconjunto al que se le debe aplicar la funcion suma

int factorial(int M){
   int num=M;
   int factor = 1;
   while (num > 0){
       factor = num * factor;
       num--;
   }
   return factor;
}
int suma(){
 
   int sum=0,j=0;
   
   while (j<length(aux)){
       sum=sum+aux[j];
       j++;      
   }
   return sum;
}

int main() {
   
   int S=5,i=0,T=0,cont=0,j,b=0,ncomb=0,k,v;
   int nc[]={0,0,0,0}; //vector que contiene el numero de combinaciones para subconjuntos de 1,2,3 y 4 elementos
   
    for (k=1;k<=length(V);k++){
       ncomb=factorial(length(V))/(factorial(k)*factorial(length(V)-k));
       printf("Numero de combinaciones con %d elementos: %d\n",k,ncomb);
       nc[k-1]=ncomb;
     }
   
   do{
       
       v=length(V);
  if(T>v || suma()>S){ //Nodo fracaso
     
      aux[i]=0;
      i--;
      T--;
      nc[k]=nc[k-1];
  }
  else if(suma()==S){ // nodo solución
     
      cont++;
      aux[i]=0;
      i--;
      T--;
      nc[k]=nc[k-1];
  }
       
       if(suma()<S) //nodo problema
       {
           T++;
           i++;
       }
 
  if(i==1 && aux[0]==V[length(V)-1]){ //Nodo solucion
      printf("Nº de soluciones %d\n",cont);
      b=1;
      exit(1);
  }
     
      ex[i]=V[i];
 
   for(j=0;j<i;j++){
       aux[j]=V[j];
       aux[i-1]=ex[i+1]++;
   }
   
   }while(b==0);
   
}







El árbol que había pensado sería el siguiente, pero si se os ocurre otro más fácil agradezco todo lo que me digáis:




Es el árbol de ejemplo que me he hecho para aclararme, pero el programa debe valer para cualquier vector de n enteros positivos.


Edito: No me he dado cuenta que falta la línea de 3 a 3,4 en el árbol.

[maritere22]

Alguien me ayuda?

[Kenkox]

Yo conozco una solución ...  seria un simple while, un arreglo y dos apuntadores y es bastante simple de entender.... El punto de este algoritmo es posicionarte en la ultima posicion de tu arreglo, e ir probando todas las combinaciones posibles... osea, estando en el ultimo elemento, probar con todas las combinaciones con ese numero, cuando hayas terminado con ese numero ahora probaras todas las combinaciones con el elemento n-2... despues de que probaste todas esas, probar con todas las combinaciones con n-3 y asi sucesivamente hasta que tu apuntador i se haga menor a 0.... el apuntador j es el auxiliar para ir probando todas las posibilidades.... por ejemplo, supongamos sumatoria = arreglo(i) + arreglo(j) donde j != i... si sumatoria > S  entonces sumatoria -= arreglo(j); j--; y entonces vuelve a entrar al ciclo......y denuevo sumatoria = arreglo(i) + arreglo(j)... y ahora supongamos que es menor... entonce j--; y volvemos a entrar... ahora supongamos que la sumatoria es igual a S.. entonces aumentamos contador de sumatorias, disminuimos i en una unidad y hacemos sumatoria = arreglo(i)... y volvemos a entrar

En resumen el apuntador i es el que te ayuda para saber el numero con el cual estas empezando, y j es con el que se va a ir sumando los numeros....

Suerte, ojalá y te sirva de algo... te daria el pseudoCodigo completo, pero el punto es que tambien pienses en terminar y programar la solucion.... y esta solucion la puedes programar ya sea en c++ o en c, o en java.. o en el lenguaje que sea... va a ser bastante similar ya que utilizas solamente herramientas basicas