[quiz] Anybody there?

[Larry Clapp]

On Tue, Jul 10, 2007 at 10:35:45PM -0500, Ivan Salazar wrote:
> 2007/7/9, Ryan Davis <ryan at acceleration.net>:
> > How about the problem in today's XKCD?: http://xkcd.com/c287.html
> OK... This is the second time I've heard of the knapsack problem.
> I've searched a little and I have some questions:
> - Are repetitions allowed (one kind of appetizer chosen more than
>   once)?

Yes.

> - Should we maximize or minimize the number of appetizers?

Either.  Whatever fits.

> If I were the waiter, it wouldn't matter if I chose an appetizer
> more than once but I'd try to carry less appetizers.
> If I were the costumer, I'd like a diverse mix (no repetitions) and
> more appetizers.
> 
> I'm thinking about programming a more general algorithm, something
> like this:
> 
> (defun serve-appetizers (menu amount &key (:with-reps nil) (:minimize t))
>  ;... lots of code
> 
> I have to do more research obviously (maybe it isn't feasible to
> program such thing, I don't now).

It's feasible to *program* it.  It's frequently not feasible to *run*
it.  NP-complete problems grow in runtime very quickly.  That is, you
can solve one in a minute for n=5, an hour for n=6, a day for n=7, and
a year for n=8 (pulling these numbers out of thin air just to
illustrate the point).

I *think* that factoring numbers is NP-complete.  Note that the
security of public-key cryptography hinges on the difficulty of
factoring large numbers.

> Have you got any particular idea or solution?

Use very small data sets.  :)

... I've said all this on the assumption that because you're
unfamiliar with the knapsack problem, you're also unfamiliar with
NP-complete problems in general (like the travelling salesman
problem); if this is not true, I apologize.

-- Larry