Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I have an expression $$Ax+By+Cz.$$ where $A$, $B$ and $C$ are positive constants $\ge1$. The variables $x$, $y$ and $z$ are non-negative integers. I am also given a number $T$.
I want to find the largest integer value such that it is less than $T$ and not satisfied by $Ax+By+Cz$, how can I do it without using brute force.
This is classical Integer Linear Programming. You have the following problem:
$$\begin{align} Ax+Bx+Cx & \to \max \\ \text{s.t} \quad x,y,z &\ge 0\\ Ax+Bx+Cx &\le T \\ x,y,z &\in \mathbb{Z}\\ \end{align}$$
There are several algorithms available for such problems. Google "branch and bound" or "branch and cut" and you will get to them.
You can picture your problem as follows. Your variables $x,y,z$ decode a grid point in 3d. The constraints cut of hyperplanes, which keeps you left with a set of candidate solutions. In your example this set is finite. You could basically test out all cancidates brute force. But it is more practical to add additional constraints to make the candidate set smaller - or in other words you filter out points. If you relax the condition that $x,y,z$ are integers, then the problem becomes much easier (Linear Programm), because then you know that the optimal point you are looking for is on some "corner" of your candidate set.
Regarding the two-dimensional case, see this answer, which proves the following two results. If $(a,b) = 1$ then every integer $x \geq (a-1)(b-1)$ is representable as $ax+by$ for some $x,y \geq 0$. Also, if $x < ab$ and $a \nmid x$, $b \nmid x$ then exactly one of $x,ab-x$ is representable.
The first result already tells you that without loss of generality, $T \leq (a-1)(b-1)$. Presumably a similar result holds in your three-dimensional case - perhaps you can assume that $T \leq (a-1)(b-1)(c-1)$. The outcome will be an algorithm running in time $\mathrm{poly}(abc)$.
