1
$\begingroup$

i want write a module to find the integer combination for a multi variable fomula. For example

$8x + 9y \le 124$

The module will return all possible positive integer for $x$ and $y$.Eg. $x=2$, $y=12$. It does not necessary be exactly $124$, could be any number less or equal to $124$. Must be as close as possible to $124$ if no exact solution could be found.

I do not want to solve with brute force as the number of variable could be any...$(5,10,100,...n)$

Any algorithm could solve this?

  • 0
    Will the formula always be less than or equal to? And that simple? (i.e., in the form $a x + b y \le c$ for integers a, b, and c)?2012-08-24
  • 0
    I am not sure if this should be tagged in "optimization" and "linear programming". You are not maximizing/minimizing a function.2012-08-24
  • 0
    http://en.wikipedia.org/wiki/Diophantine_equation, maybe this is where you are looking for? You can use Euclids' Algorithm to solve $ax+by=c$. http://en.wikipedia.org/wiki/Euclidean_algorithm2012-08-24
  • 0
    The number of variable could be any not just x and c, could be n variable. Thanks for tiping, all is welcome.2012-08-25
  • 0
    X and Y sory fot the typo2012-08-25
  • 0
    @KartikAudhkhasi: "Must be as close as possible to 124 if no exact solution could be found."2012-09-23

3 Answers 3