[algogeeks] Re: Buying candy Don Tue Feb 28 10:01:03 2012
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 - -- 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.