Dado un conjunto de números (en este caso):
3, 7, 7, 100, 50
O bien:
demostrar que es imposible formar el número k = 190 utilizando los operadores ( ) + - * / entre el subconjunto de estos números ex: 1000 = ((3 + 7) * 100)
o
encuentra la expresión que sí forma el número k = 190.
No estoy seguro de cómo trabajar en este problema analíticamente ya que el caso general de cualquier subconjunto y cualquier número k parece ser un problema NP Hard.
Deseo forzar la solución para esto. ¿Es suficiente el siguiente algoritmo?
Tome el conjunto F: Calcule todos los posibles subconjuntos ordenados de F (¿Cómo hacer esto de forma elegante?)
Calcula todas las combinaciones posibles de operadores entre cada subconjunto ordenado...
Si alguno es igual a 190 entonces el problema está resuelto, si ninguno es igual a 190 entonces claramente no es posible.
¿Cómo se diseña en general este algoritmo? ¿Hay una forma mejor de resolver este problema (preferiblemente sin fuerza bruta)?
Mi intento de análisis:
Quería ver si trabajando con el número módulo Q sería fácil filtrar qué posibles expresiones pueden evaluarse a 190. Ya que la expresión S = 190 debe ser verdadera mod Q para todo Q si es verdadera.
Mi otro intento de fuerza bruta:
A partir de 190, sistemáticamente, se suman, restan, dividen, etc... expresiones del conjunto original con la esperanza de que una de estas cadenas expresivas concluya en un valor que todavía esté presente en el conjunto. Esto parece ser tan costoso computacionalmente como el método anterior (¿Cómo podría implementar esto?)
