Algoritmo No determinista para un problema
Publicado por anahi (1 intervención) el 16/11/2018 00:40:26
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 se lo podria considerar algoritmo polinomial no determinıstico
Realice esto pero no se si se lo podria considerar algoritmo polinomial no determinıstico
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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;
}Valora esta pregunta
0