2
$\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
    @KartikAudhkhasi: "Must be as close as possible to 124 if no exact solution could be found."2012-09-23

3 Answers 3

1

You are trying to solve

${\rm maximize} 8x + 9y$ subject to $8x + 9y \le 124$ $ x, y \in \mathbb{Z}^+$

Which is essentially a special case of the knapsack problem. ${\rm maximize} \sum_i a_i x_i \le b$ subject to $\sum_i a_i x_i \le b$ $ x_i \in \mathbb{Z}^+$ This can be solved with a MIP solver.

  • 0
    Assuming $x,y\geq 0$ for the Knapsack problem.2012-10-30
0

Considering the equal case, if you analyze some of the data points that produce integer solution to the original inequality:

$...,(-34,44), (-25,36), (-16,28), (-7,20),(2,12),(11,4),...$

you can see that: $x_{i}=x_{i-1}+9$

to get $y$ values, re-write the inequality as follows (and use the equal part):

$y = \frac{124-8x}{9}$

using the above equations you can find $(x,y)$ values in a given range of $x$ values without brute force.

0

Given a finite set $U$ of positive integers, and positive integers $B$ and $K$, the problem of determining whether there are non-negative integers $a(u)$ such that $K\le\sum_{u{\rm\ in\ }U}a(u)u\le B$ is NP-complete (which implies that it is computationally infeasible now and, perhaps, forever). This is discussed under the heading Integer Knapsack on page 247 of Garey and Johnson, Computers and Intractability. As has been pointed out already, it's easy if $\#U=2$.