In general, a solution to the linear diophantine equation ax + by = c has the form:

x = x0 + b/d t,

y = y0 - a/d t,

where (x0, y0) is any particular solution (which can be found by extended gcd), d = gcd(a, b), and t is an integer parameter.

Let's investigate for which values of t the solution is feasible for our problem (x and y are non-negative):

x0 + b/d t >= 0, y0 - a/d t >= 0, a >= 0, b >= 0, =>

-x0*d/b <= t <= y0*d/a.

And since t must be an integer, we futher have: ceil(-x0*d/b) <= t <= floor(y0*d/a).

So, all the feasible values of t form an interval of consecutive integer values.

Next, let's look at the cost function: c1 x + c2 y = (c1 x0 + c2 y0) + (c1 b/d - c2 a/d) t = (some const) + (another const) * t, i.e. it's linear in t, which means that its minimum and maximums can occur only at the boundary of feasible region.

So, just check two points t=ceil(-x0*d/b), and t=floor(y0*d/a), and choose whichever one is cheaper.

fR0D wrote:can sumbdy plz ...

Oh, for god's sake, use proper English and a spellchecker!

I won't reply to any more posts written in that style.