Verificar que la entrada es la suma de otros números

Question

Tengo una relación:

4000k + 2500j + 400g = n, k >= 0, 0 <= j <= k, 0 <= g <= j

Tengo que hacerlo, dado n Verifica que existe una solución. Voy a implementar esto como un validador en un sitio web, por lo que las soluciones informáticas están bien.

Hasta ahora, he podido escribir el validador como una serie de tres bucles anidados, pero estoy buscando una opción de mejor rendimiento, aunque sea tan simple como eliminar uno de los bucles.

También he probado WolframAlpha, pero no me ha servido de mucho más que para simplificar un poco algunas expresiones.

Answer 1

Además de la excelente solución de mniip, el Número de Frobenius de (69,65,40) es, según alfa , 691. Por lo tanto, todos $m\ge 692$ tienen una solución, $m=691$ no tiene solución, y para $m\le 690$ necesitas comprobarlo.

Answer 2

En primer lugar, obviamente, hay que comprobar si $n$ es divisible por $100$ Si es así, digamos que $m=n/100$ y nos quedamos con

$$40k+25j+4g=m\\0\le g\le j\le k$$

Ahora, dejemos que $j=g+j_g$ , donde $j_g\ge 0$ debido a la desigualdad anterior, y $k=j+k_g=g+j_g+k_j$ , donde $k_j\ge 0$ . Sustituyendo esto obtenemos:

$$69g+65j_g+40k_j=m\\g,j_g,k_j\ge 0$$

A partir de ahí es una simple recursión dinámica o de otro tipo con memoización.

También hay un enfoque aún más eficiente que el dinámico: podríamos reescribir la pregunta de "hay una solución" a "cuántas soluciones hay" y obtener la siguiente relación recurrente:

$$F_m=\left\{\begin{array}{lr}0&m<0\\1&m=0\\F_{m-69}+F_{m-65}+F_{m-40}&m>0\end{array}\right.$$

Que, al ser una recurrencia lineal con coeficientes constantes, se puede calcular de forma cerrada.