@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? -- 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.
