Un pequeño y divertido problema

Question

Digamos que tengo un conjunto de enteros no negativos $a_1,..,a_n$ y un número $C$ que es una constante no negativa (un número entero).

Considere una ecuación

$x_1\cdot a_1 + x_2\cdot a_2 + ... + x_n\cdot a_n - C = 0$

donde $x_1,...,x_n$ son enteros no negativos desconocidos. Tengo que decir si existe una solución a esta ecuación, y cuándo existe y cuándo no existe.

Agradecería mucho la ayuda de cualquiera, llevo un buen rato luchando con esto.

EDITAR
Bueno hasta ahora no he avanzado mucho, me voy a dormir y nos vemos en la mañana.Hasta ahora tengo dos conclusiones. 1.) si el número C no es divisible por el gcd del conjunto entonces no hay solución 2.) si C es divisible por el gcd, si dividimos todos los números por el gcd entonces se convierte en el problema de la moneda de Frobenius.

Answer 1

Esta forma es realmente ineficiente para un gran número de variables, pero la Programación Entera es una característica incorporada en la mayoría del software de cálculo científico en estos días.

Intenta encontrar si este programa de números enteros tiene solución

$$\mathbf{min} \sum_ix_i$$ $$s.t. \sum_i a_i x_i = C$$ $$x_i \geq0$$ donde todos $x_i$ son números enteros. Esto le dará un sucio pero la respuesta es fácil.

Nota : La función objetivo $\sum x_i$ es sólo un marcador de posición. Puede ser sustituido por cualquier otra función creciente. Si el software lo soporta, incluso $\mathbf{min}\mbox{ } 0$ está bien. Gracias a Jacob por señalarlo.

Answer 2

Resolverlo como problema de la mochila . $a_i$ es su peso, $x_i$ es la cantidad de cada artículo y establece el "valor" de cada $x_i$ como 1. $C$ es el peso total que puede llevar tu mochila. Si encuentras una solución, comprueba si el "peso" total es igual a $C$ entonces tienes una solución.