Given two numbers $a$ and $b$. We need to find all the linear combinations i.e $$ax+by \le N$$ such that $x \geq 0$ and $y \geq 0$. Please notice the non-negative constraint.
What is the smallest possible remainder left when tiling $N$ using the numbers $a$ and $b$. This is also equivalent to finding the largest possible number less than or equal to $N$ expressible as the linear combination of $a$ and $b$ as this will minimize the left over / remainder in $N$. We can only use the numbers $a$ and $b$ positive or zero number of times (no negatives allowed, zero is okay). This is just like knapsack but using two weights.
Please help me find a super optimized strategy to solve this interesting problem.
Some fact I found is that linear combination is a multiple of gcd of the two numbers, i.e $$ax + by = k\cdot gcd(a,b)$$
The generic solution is easily found out using Bezouts identity and its counterpart Extended euclidean algorithm. But the problem here is the coefficients cannot be negative.
Lets hope to find some interesting solutions.
$ax + by = N$ always has integer solutions in $x, y$ iff $\gcd(a,b)|N$. If $\gcd(a,b)\not|N$ then there are no solutions. The smallest positive $k$ such that $\gcd(a,b)|N-k$ will give you the smallest possible remainder after tiling $N$ with a linear combination of integers $a,b$.
Example 1:
$$2x + 3y \le 10$$
If we solve for $2x + 3y = 10$ we get $(x_0, y_0) = (5,0)$ and the general solution is $x = 5 - 3 n, y = 2 n$ and $n \in \mathbb{Z}$. If we add the condition $x \ge 0, y \ge 0$, we get $5-3n \ge 0, 2n \ge 0$.
Example 2:
$$2x + 2y \le 11$$
In this case, $\gcd(2,2) = 2 \not|11$.
So, we check $2x + 2y = 10 \implies x + y = 5$ which has $0 \le x \le 5$ and $y = 5-x$ as solutions. Therefore, the smallest remainder is $k = 11 - 10 = 1$.