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.