Se trata de una especie de rompecabezas estándar, que muchos lo hacen por medio de ensayo y error o el método de fuerza bruta. La pregunta va así, dadas las cifras, 11,13,31,33,42,44,46 Qué es opciones de números (un número puede ser elegido más de una vez) así que eso suma añade hasta 100.
¿Hay una fórmula como forma o enfoque a esto que no sea fuerza bruta solamente?
SUBCONJUNTO de la SUMA es NP-completo, por lo que en general es difícil saber incluso si hay una opción de números que se suma a un objetivo determinado.
EDIT: Morón se ha planteado el punto válido que los números pueden ser reutilizados. Por lo tanto, sustituir cada número $x$ con una secuencia $x,2x,4x,\ldots,2^kx,\ldots$, deteniéndose antes de llegar a un número mayor de nuestro destino.
Vamos a analizar detenidamente el estallido de tamaño. Supongamos que los números originales de $x_i$ tenían el tamaño de la $l_i$, y el de destino $T$ tenían el tamaño de la $L$. Reemplazamos cada número $x_i$ $L$ números de tamaño en la mayoría de las $L$, y para el nuevo tamaño es $$\sum_i L^2 + L \leq L^2 (\sum_i x_i + L),$$ de modo que la voladura se encuentra en la mayoría cúbicos, y en particular polinomio. Así que el problema es NP-duro (es trivialmente en NP): no, ya que la reducción es en la dirección equivocada... (gracias, Idiota, para darse cuenta de)
Suponiendo que los números son enteros positivos,
Esto está estrechamente relacionado con el Frobenius de la Moneda Problema que dice que hay un número máximo $\displaystyle F$ (llamado el número de Frobenius), que es no representable. Es NP-Difícil de encontrar el número de Frobenius cuando hay, al menos, $\displaystyle 3$ números.
Para una fórmula como enfoque para determinar si este tipo de representación es posible o no, puede utilizar funciones de generación, el cual puede ser utilizado para dar una pseudo polinomio de tiempo de un algoritmo polinomial en el tamaño de la $\displaystyle W = n_1 + n_2 + \cdots + n_k$.
Si los números son $\displaystyle n_1, n_2, \dots, n_k$ y que necesita para ver si pueden ser resumidos de la a$\displaystyle S$, entonces el número de maneras en que se puede hacer es el coeficiente de $\displaystyle x^S$ en
$$\displaystyle (1+x^{n_1} + x^{2n_1} + x^{3n_1} + \cdots )(1+ x^{n_2} + x^{2n_2} + x^{3n_2} + \cdots ) \cdots (1 + x^{n_k} + x^{2n_k} + x^{3n_k} + \cdots )$$
$$\displaystyle = \dfrac{1}{(1-x^{n_1})(1-x^{n_2}) \cdots (1-x^{n_k})}$$
El uso parcial de las fracciones esto puede ser escrito como
$$\displaystyle \sum_{j=1}^{m} \dfrac{C_j}{c_j - x}$$
donde $\displaystyle C_j$ $\displaystyle c_j$ son apropiados los números complejos y el $\displaystyle m \le n_1 + n_2 + \cdots + n_k$.
El coeficiente de $\displaystyle x^S$ es dada por
$$\displaystyle \sum_{j=1}^{m} \dfrac{C_j}{c_j^{S+1}}$$
que tiene que comprobar es cero o no.
Por supuesto, esto podría requerir bastante precisa de operaciones de punto flotante y no dicen realmente lo que los números a elegir.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
