Loading...

algogeeks@googlegroups.com

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

[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.