Algorithm Non-deterministic For a problem

Question

Algorithm Non-deterministic For a problem

Navigation

#1 by (0 votes)

0

Given a set A of integers and an integer s, the exact sum problem consists of in determining if there exists a subset B ⊆ A such that the elements of B add s. I need to write a non-deterministic polynomial algorithm for this problem.

Do this but I do not know if it would be fulfilled.

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

algoritmos

asked by Anahi 15.11.2018 в 19:19

source

1 answer

concatenate two outputs for each or make them into one java Excel in php report

score 0 · Answer 1

public static void main(String[] args) {
    int []numeros= {1,2,3,4,5};
    boolean []elegidos=new boolean[numeros.length];
    boolean solucion=false;
    int k=6;
    while(solucion==false && suma(numeros)>=k)
    {
        solucion=solucion(numeros,elegidos,k);
    }

    for(int i=0;i<elegidos.length;i++)
    {
        if(elegidos[i]==true)
        System.out.println(numeros[i]);

    }

}

static int suma(int []numeros)
{
    int suma=0;
    for(int i=0;i<numeros.length;i++)
        suma+=numeros[i];
    return suma;
}
static boolean solucion(int []numeros,boolean[]elegidos,int k)
{

    for(int i=0;i<numeros.length;i++)
    {
        Random aleatorio = new Random();
        // Producir nuevo int aleatorio entre 0 y 99
        boolean intAleatorio = aleatorio.nextBoolean();

        elegidos[i]=intAleatorio;
    }
    int suma=0;
    for(int i=0;i<elegidos.length;i++)
    {

        if(elegidos[i]==true)
        suma+=numeros[i];
    }


    return suma==k;
}