0

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);
}
5
  • Pero intentaste algo? en algun lenguaje? Tene en cuenta que aca no se hacen ejercicios, salvo que demuestres que intentaste algo y te trabaste en una parte en particular.
    – gbianchi
    Commented el 15 nov. 2018 a las 18:23
  • Si, acabo de editar.
    – Anahi
    Commented el 15 nov. 2018 a las 18:39
  • 1
    ok.. que lenguaje es? puede ser java o C#.. si cumpliria con que? en tal caso, que requisitos debe cumplir? como los validaste?
    – gbianchi
    Commented el 15 nov. 2018 a las 18:45
  • Si se puede decir que es un algoritmo no determinista. Y es Java
    – Anahi
    Commented el 15 nov. 2018 a las 18:46
  • no parece para nada. No hay nada aleatorio en el y por lo tanto hay un solo resultado posible. Vos que pensas al respecto?
    – gbianchi
    Commented el 15 nov. 2018 a las 18:49

1 respuesta 1

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

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.