And as a matter of fact , this seems to be the best solution as well- clearly greedy fails here. e.g in the example given : we have cups of capacity 3, and 5. We can also use capacity of 5-3=2. So we can use 5 or 3 or 2 literse. The greedy choice to fill 4 liters should first fill in 3 litres and then it has no way of filling remaining 1 litre. Clearly best approach would be to fill using 2 litres twice. ( 2*4 = 8 operations) . However because last one is A-B type , we subtract one and get 7 operations.
So only dp works and greedy fails. But however if you have capacities of A and B in some spcl constraint , we can use greedy as well. For example consider cups of size 4 litres and 6 litres. :P I think we can make greedy if A-B is smallest and divides both A and B. then we can always use greedy. // we need A-B to be smallest just because number of operations required are more for this . On Mon, Oct 26, 2009 at 12:06 PM, nikhil garg <nikhilgar...@gmail.com>wrote: > 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- > > -- 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 -~----------~----~----~----~------~----~------~--~---
