Skip to main content
se añadieron 1089 caracteres en el cuerpo
Origen Enlace

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);
}

Dado un conjunto A de enteros, el problema de partición consiste en determinar si existe un subconjunto B ⊆ A tal que los elementos de B suman lo mismo que los elementos de A\B. Quiero escribir un algoritmo polinomial no deterministico para este problema. Pero no se me ocurre como hacerlo. Gracias.

Dado un conjunto A de enteros y un entero s, el problema de suma exacta consiste en determinar si existe un subconjunto B ⊆ A tal que los elementos de B suman s. Necesito escribir un algoritmo polinomial no determinıstico para este problema.

Realice esto pero no se si 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);
}
Origen Enlace

Algoritmo No deterministico Para un problema

Dado un conjunto A de enteros, el problema de partición consiste en determinar si existe un subconjunto B ⊆ A tal que los elementos de B suman lo mismo que los elementos de A\B. Quiero escribir un algoritmo polinomial no deterministico para este problema. Pero no se me ocurre como hacerlo. Gracias.