How would you maximize the following function (with integer domain) $$f(x,y) = a * x + b * y$$ subject to $$c * x + d * y \leq N$$ $$x \geq 0, y \geq 0$$ the constants $a, b, c, d, N$ are known nonnegative integers.
I can see how this becomes trivial if $N$ is a multiple of $lcm(c, d)$ but I can't see the solution in the general case.
Regards.
How about using Lagrange multiplier?
Because there are inequality constrains we need to make some modification, i.e. use KKT conditions. The fact that the function is linear will make things easier. So after applying Lagrange multipler the function should look like:
$$F(x,y,\lambda,\lambda_1,\lambda_2) = ax + by + \lambda(x) + \lambda_1(y) - \lambda_2(cx + dy - N)$$
Now we take partial derivatives and we set the to 0:
$$F_x = a + \lambda - \lambda_2c = 0$$ $$F_y = b + \lambda_1 - \lambda_2d = 0$$
Because the terms we've added must be equal to 0, now we have to check $2^3 = 8$ distinct cases. You can read more here and apply the new things depending on the constants $a,b,c,d,N$.
Note that you can exclude the terms $\lambda(x) + \lambda(y)$ and apply Lagrange multiplier only to the last constrain and the check whether the obtained solution are in the bounded region (in this case $x,y\ge0$). But I recommend using them just to make double sure. If you decide to leave them and you don't obtain a solution then the stationary point is on the boundary of the region. We check the cases: $x=0$, $y=0$ and then both $x=y=0$