How to find that a number is a sum of multiple of different numbers?

Question

Suppose a product comes in packs of 3, and 5, and a customer demands 8 quantities of that product.

1 = (1)3 + (1)5

But, if a customer demands 4 products, it isn't possible, there is no solution that can give you the sum 7 for the packs of 3, and 5.

My approach:

n = (x)a + (y)b

a and b are quantities in two packs, and x & y are to be determined. I'll apply different combination starting from (0,1), (1,0), (1,1) till (b,b) assuming b > a. I don't know what this problem is called in Mathematics. Is there a solution already developed for it, or what would be the best approach for it?

Pardon my English, and the way I wrote this question. I'm just a beginner.

---

Edit: The number of total packs can vary. In above statement, there were 2 packs available, and in general, it can be n pack where is any positive integer greater than 1.

Answer 1

There is a very simple algorithm which determines if the solution exists or not, a problem very close to this is the Frobenius coin problem.

So suppose you have packages of sizes $a$ and $b$, we can assume $a$ and $b$ are coprime, otherwise make the suitable modifications. For a given $n$ you wish to find non-negative integers $x$ and $y$ so that $xa+yb=n$.

Here is the algorithm you need:

First take $x=na^{-1}\bmod b$ and reduce it (so that $x=\{0,1,2\dots b-1\}$).

Notice that $\frac{n-xa}{b}$ will be an integer, if it is negative there is no solution, otherwise taking $y=\frac{n-xa}{b}$ gives the solution.

Here is the napsack c++ code, it runs in time $N\times K$ ($N$ is desired number and $K$ is the number of sizes).

#include <bits/stdc++.h>
using namespace std;

const int MAX=100010;
int V[MAX]; // V[i] is 0 if we cant form i, otherwise it stores a possible summand.
int S[MAX]; // stores how many times each number is used to add N.

int main(){
    int K,N; // K is the number of sizes and N the desired number.
    scanf("%d %d",&N,&K);
    V[0]=1;
    while(K--){
        int x; 
        scanf("%d",&x); //every time we read a number we update the values we can form
        for(int j=x;j<=N;j++){
            if(V[j]==0 && V[j-x]) V[j]=x; // if we can form j-x we can form j
        }
    }
    if(V[N]){
        int M=N;
        while(M){ // we start substracting the summands of M and adding them to S[]
            S[V[M]]++; 
            M-=V[M];
        }
        for(int i=0,t=0;i<=N;i++){ // here we just print the result.
            if(S[i]){
                if(t) printf(" + ");
                printf("%d(%d)",S[i],i);
                t=1;
            }
        }
        printf("\n");
    }
    else printf("Impossible");
}