We at any one step can measure only 3 quantities: A liters , B liters , or (A-B) litres. ( assuming A>B) With every operation we have a cost associated: For A liter , we need 2 operations( Fill A , transfer from A to vessel) . For B liter , similarly we need 2 operations And for (A-B) litres we need 4 operations in general ( fill A , transfer A to B, transfer remaining A to vessel and spill B. ) However if this is the last operation , we dont need to empty B so in that case it would take 3 moves.
But for the moment assume A takes 2 operations , B takes 2 and A-B takes 4. So see this as a variation of standard Coin Change problem or use simple DP to find the optimal number of operations. Check if in the optimal solution , last move is A-B , if yes, subtract 1 from the answer found ( we dont need to spill B now ) cheers On Mon, Oct 26, 2009 at 9:23 AM, shah zeb <sftra...@yahoo.com> wrote: > http://eaziweb.blogspot.com/ > > Regards > Shahzeb Farooq > Chohan > > > ------------------------------ > *From:* ShingRay <masterrays...@gmail.com> > *To:* Algorithm Geeks <algogeeks@googlegroups.com> > *Sent:* Sunday, October 25, 2009 14:59:58 > *Subject:* [algogeeks] Pouring Water Problem > > > Given two cups, one of which can contain A litres of water and the > other can contain B litres of water, find out the minimum number of > steps required to obtain C litres of water in a vessel. > > At the beginning both cups and the object vessel are empty. > These are feasible operations: > 1 emptying a cup > 2 pouring water from a cup to the other or the vessel > 3 filling a cup > > For example, when A is 3, B is 5 and C is 4, the minimum number of > steps is 7. > (*) You can fill B, and pour water from B to A, then pour water from B > to the vessel. > The three operations obtain 2 litres of water. We empty A and repeat > (*). We obtain another 2 litres and it takes 7 steps. > > More examples: > A B C minimum > 1 2 1 2 > 1 2 9 10 > 3 5 12 7 > 6 7 20 6 > > ----- > > A*x + B*y = C > If x, y are both no non-negative, it takes (x+y)*2 steps. > If one of them is negative, it takes (x+y)*2-1 steps. > > We can iterate x from -max(A, B, C) to max(A, B, C) and get many x-y > tuples, each of which denote a solution. The minimum solution is the > best. > I think the iteration range can be reduce. > What is a more effective algorithm? > > ------------------------------ > New Email addresses available on Yahoo! > <http://sg.rd.yahoo.com/aa/mail/domainchoice/mail/signature/*http://mail.promotions.yahoo.com/newdomains/aa/> > Get the Email name you've always wanted on the new @ymail and @rocketmail. > Hurry before someone else does! > > > > -- nikhil- --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
