[algogeeks] Re: Buying candy Don Tue Feb 28 10:01:34 2012
Dave's answer, the Hungarian Algorithm, is correct because it does meet the requirements of the problem. There is another algorithm called Jonker-Volgenant-Castanon (JVC) which can be proven to be faster both on average and in worst case, than the Hungarian Algorithm. Both solutions are sure to find the best solution, which is not true of any ad hoc or greedy algorithm. For years, the Munkres algorithm was the best known solution, but JVC is significantly faster than Munkres. Don On Feb 28, 11:39 am, Don <[EMAIL PROTECTED]> wrote: > Yes, the tags constrain him to buy exactly one candy from each row and > each column. > There is a slightly better algorithm than Hungarian. > Don > > On Feb 28, 11:33 am, Dave <[EMAIL PROTECTED]> wrote: > > > > > @Don: Based on your example, there seems to be an unstated requirement > > that Bob can and must buy exactly one candy from each row and each > > column. > > > This is an assignment problem (see en.wikipedia.org/wiki/ > > Assignment_problem), and can be solved in O(N^3) by the Hungarian > > Algorithm (see en.wikipedia.org/wiki/Hungarian_algorithm). > > > Dave > > > On Feb 28, 9:27 am, Don <[EMAIL PROTECTED]> wrote: > > > > Little Bob likes candy, and he wants to buy all the candy he can get > > > for the smallest price. At the store there is a big table with candy > > > arranged in an NxN grid. Each candy has a price, Pij where i is the > > > row and j is the column in which the candy is located. The store owner > > > gives Bob N tags numbered 1..N. Bob can place one tag at the top of > > > each column indicating the piece of candy he will buy from that > > > column. > > > > Bob is smart enough to realize that he should not always buy the least > > > expensive candy. For example, consider this price grid: > > > > 1 20 > > > 5 50 > > > > In this case, buying the candy priced 1 would force him to buy the > > > candy priced 50, for a total cost of 51. He is better off buying the > > > second candy in the first column, allowing him to buy the first candy > > > in the second column for a total price of 25. > > > > For a 2x2 case, considering all the possibilities is easy enough. > > > There are only two choices. But as N increases, the number of ways to > > > select N candies increases as N!, and Bob doesn't have time for an > > > algorithm which requires more than polynomial time to execute. > > > > What algorithm should Bob use to buy N pieces of candy for the > > > smallest cost?- Hide quoted text - > > > - Show quoted text -- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.