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 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?hl=en.
