Dado un conjunto A de enteros y un entero s, el problema de particiónsuma exacta consiste en en determinar si existe existe un subconjunto B ⊆ A tal que los elementos de B suman lo mismo que los elementos de A\Bs. QuieroNecesito escribir un algoritmo polinomial no deterministicodeterminıstico para este problema. Pero
Realice esto pero no se me ocurre como hacerlo. Graciassi cumpliría.
public static void main(String[] args) {
int []numeros= {1,2,3,4};
int []elegidos= new int [numeros.length];
System.out.println(buscarSubconjunto(numeros,0,numeros.length,4,elegidos));
for(int i=0;i<elegidos.length;i++)
if(elegidos[i]==1)
System.out.println(numeros[i]);
}
static boolean buscarSubconjunto(int []cifras, int j,int cantidadDeElementos,int k,int elegidos[]){
boolean temp;
if(j==cantidadDeElementos)// (* no hay más números en el conjunto *)
return false;
if (k==0)
return true;
if(cifras[j]>k)// (* el número sobre el cual se está decidiendo es mayor que el objetivo *)
return buscarSubconjunto(cifras,j+1,cantidadDeElementos,k,elegidos);
elegidos[j] =1;//(* registra que el número cifras[j] va en el subconjunto solución *)
temp = buscarSubconjunto(cifras,j+1,cantidadDeElementos,k-cifras[j],elegidos);
if (temp)
return true;
elegidos[j] = 0;// (* registra que el número cifras[j] no va en el subconjunto solución *)
return buscarSubconjunto(cifras,j+1,cantidadDeElementos,k,elegidos);
}