Loading...

algogeeks@googlegroups.com

[Prev] Thread [Next]  |  [Prev] Date [Next]

[algogeeks] Buying candy Don Tue Feb 28 08:00:46 2012

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.