Problems? Is your data what you think it is?  
PerlMonks 
Re: Challenge: N Jugs Problemby blokhead (Monsignor) 
on Apr 14, 2009 at 18:58 UTC ( #757463=note: print w/ replies, xml )  Need Help?? 
Update: elaboration on the above paragraph. Suppose aX + bY = gcd(X,Y). Then one of {a,b} is positive and one is nonpositive. Suppose a is positive. Then here is how you get gcd(X,Y) units in the Xunit 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 3unit 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 changemaking problem, where it is known that the greedy algorithm may not always work (for the generalized problem with more than 2 jugs/denominations). blokhead
In Section
Seekers of Perl Wisdom

