11 Jul
2007
11 Jul
'07
12:59 p.m.
On Tue, Jul 10, 2007 at 10:35:45PM -0500, Ivan Salazar wrote: > 2007/7/9, Ryan Davis <ryan@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