¿Cómo encontrar que un número es una suma de múltiplos de diferentes números?

Question

Supongamos que un producto viene en paquetes de 3 y 5, y un cliente demanda 8 cantidades de ese producto.

1 = (1)3 + (1)5

Pero, si un cliente demanda 4 productos, no es posible, no hay ninguna solución que pueda darte la suma 7 para los paquetes de 3 y 5.

Mi enfoque:

n = (x)a + (y)b

a y b son cantidades en dos paquetes, y x & y deben ser determinados. Aplicaré diferentes combinaciones empezando desde (0,1), (1,0), (1,1) hasta (b,b) asumiendo que b > a. No sé cómo se llama este problema en Matemáticas. ¿Ya hay una solución desarrollada para esto, o cuál sería el mejor enfoque?

Perdonen mi inglés, y la forma en que escribí esta pregunta. Soy solo un principiante.

---

Editar: El número de paquetes totales puede variar. En la declaración anterior, había 2 paquetes disponibles, y en general, puede ser n paquete donde n es cualquier entero positivo mayor que 1.

Answer 1

Hay un algoritmo muy simple que determina si la solución existe o no, un problema muy cercano a esto es el problema de las monedas de Frobenius.

Entonces supongamos que tienes paquetes de tamaños $a$ y $b$, podemos asumir que $a$ y $b$ son coprimos, de lo contrario, hacer las modificaciones adecuadas. Para un dado $n$ deseas encontrar enteros no negativos $x$ y $y$ de manera que $xa+yb=n$.

Aquí tienes el algoritmo que necesitas:

Primero toma $x=na^{-1}\bmod b$ y redúcelo (para que $x=\{0,1,2\dots b-1\}$).

Observa que $\frac{n-xa}{b}$ será un entero, si es negativo no hay solución, de otra forma tomando $y=\frac{n-xa}{b}$ obtienes la solución.

Aquí está el código en c++ de la mochila, se ejecuta en tiempo $N\times K$ ($N$ es el número deseado y $K$ es el número de tamaños).

#include 
using namespace std;

const int MAX=100010;
int V[MAX]; // V[i] es 0 si no podemos formar i, de otra forma almacena un sumando posible.
int S[MAX]; // almacena cuántas veces se utiliza cada número para sumar N.

int main(){
    int K,N; // K es el número de tamaños y N es el número deseado.
    scanf("%d %d",&N,&K);
    V[0]=1;
    while(K--){
        int x; 
        scanf("%d",&x); //cada vez que leemos un número actualizamos los valores que podemos formar
        for(int j=x;j<=N;j++){
            if(V[j]==0 && V[j-x]) V[j]=x; // si podemos formar j-x podemos formar j
        }
    }
    if(V[N]){
        int M=N;
        while(M){ // comenzamos restando los sumandos de M y agregándolos a S[]
            S[V[M]]++; 
            M-=V[M];
        }
        for(int i=0,t=0;i<=N;i++){ // aquí solo imprimimos el resultado.
            if(S[i]){
                if(t) printf(" + ");
                printf("%d(%d)",S[i],i);
                t=1;
            }
        }
        printf("\n");
    }
    else printf("Imposible");
}