# An integer linear program

I have the following problem:

Given positive integers $a, b, c, d, n$, compute the maximum possible value (which is garuanteed to be less than $10^9$) of the function $$f(x,y) = cx + dy$$ where the only pairs $(x, y)$ that are considered for which $x$ and $y$ are positive integers and $ax + by \leq n$.

I'll be very grateful for any tips about which method could be used to solve this.

• 1. What's the source for this problem? It's good practice to always attribute your sources and give credit to where you got this from. Is this from a live coding contest? 2. Are you taking a class? What material do you know that might be relevant? I know of multiple possible approaches, at different levels of mathematical and algorithmic sophistication; giving us some information about what you already know will help us tailor answers to your level of understanding. – D.W. Aug 15 '16 at 21:30
• 3. What approaches have you already considered? What's the best algorithm you've come up with so far? This site works best when you show us what progress you've already made, rather than copying the problem statement and expecting us to hand you a solution on a platter. You mentioned integer linear programming. Have you tried using an off-the-shelf ILP solver? 4. The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – D.W. Aug 15 '16 at 21:30
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Aug 15 '16 at 22:17
• @RodrigoDeAzevedo Thanks for the edit, but how is this title any better? – Raphael Oct 17 '16 at 12:47
• @Raphael "Integer Linear Programming" (ILP) was the previous title. ILP is a problem, whereas the question is on an instance of ILP. I think the difference is stark. – Rodrigo de Azevedo Oct 17 '16 at 12:52