in reply to Challenge: N Jugs Problem
Update: elaboration on the above paragraph. Suppose aX + bY = gcd(X,Y). Then one of {a,b} is positive and one is non-positive. Suppose a is positive. Then here is how you get gcd(X,Y) units in the X-unit jug:
- Do this "a" times: Fill the X-jug and dump as much as you can into the Y-unit jug.
- If the Y-jug fills during this step, and you have dumped the Y-jug less than |b| times, then dump the Y-jug on the ground and continue to empty the X-jug into the Y-jug.
- Once you have dumped the Y-jug |b| times, there will be aX - |b|Y = aX + bY = gcd(X,Y) left in the X-jug, which you can pour into the target jug
BTW, the greedy approach won't necessarily work either. The greedy approach is (assuming X>Y): fill in increments of X as many times as you can, then fill in increments of Y as many times as you can, then somehow obtain the remaining amount to be filled, if any.
For instance, with X=5, Y=3, and target = 6, the best you can do is fill the 3-unit jug twice. The greedy algorithm would first put 5 units in the target jug, then try to get 1 unit into the target jug, which will certainly take more steps.
In fact, if you restrict the target amount to something that is expressible as a positive linear combination of X and Y, you have an equivalent of the change-making problem, where it is known that the greedy algorithm may not always work (for the generalized problem with more than 2 jugs/denominations).
blokhead