[quiz] Anybody there?

[Ivan Salazar]

2007/7/11, Larry Clapp <larry at theclapp.org>:
> 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
>
> _______________________________________________
> quiz mailing list
> quiz at common-lisp.net
> http://common-lisp.net/cgi-bin/mailman/listinfo/quiz
>
OK, was this quiz a joke then? u_u