[quiz] Anybody there?
It sounds interesting. I'd like to join in, even if I'm a real newbie. Have you got any ideas?
How about the problem in today's XKCD?: http://xkcd.com/c287.html Ryan Davis Acceleration.net Director of Programming Services 2831 NW 41st street, suite B Gainesville, FL 32606 Office: 352-335-6500 x 124 Fax: 352-335-6506 Ivan Salazar wrote:
It sounds interesting. I'd like to join in, even if I'm a real newbie. Have you got any ideas? ------------------------------------------------------------------------
_______________________________________________ quiz mailing list quiz@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/quiz
2007/7/9, Ryan Davis <ryan@acceleration.net>:
How about the problem in today's XKCD?: http://xkcd.com/c287.html
Ryan Davis Acceleration.net Director of Programming Services 2831 NW 41st street, suite B Gainesville, FL 32606
Office: 352-335-6500 x 124 Fax: 352-335-6506
Ivan Salazar wrote:
It sounds interesting. I'd like to join in, even if I'm a real newbie. Have you got any ideas?
------------------------------
_______________________________________________ quiz mailing list quiz@common-lisp.nethttp://common-lisp.net/cgi-bin/mailman/listinfo/quiz
_______________________________________________ quiz mailing list quiz@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/quiz
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)? - Should we maximize or minimize the number of appetizers? 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). Have you got any particular idea or solution? Iván.
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
2007/7/11, Larry Clapp <larry@theclapp.org>: > 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 > > _______________________________________________ > quiz mailing list > quiz@common-lisp.net > http://common-lisp.net/cgi-bin/mailman/listinfo/quiz > OK, was this quiz a joke then? u_u
On Wed, Jul 11, 2007 at 04:07:53PM -0500, Ivan Salazar wrote:
OK, was this quiz a joke then? u_u
Well, I didn't propose it. I don't know what the guy who suggested it had in mind, one way or the other. I initially thought it would be a hard problem (or at least take a long time to solve), thus my cautionary remarks, but the solution posted here earlier took ~0.001 seconds on my machine. I guess this dataset was sufficiently small. :) -- L
I submitted it half-jokingly, but I figured the dataset was small enough that it'd still complete, and the comic makes it a little more fun to dig into. It's also a nice example of NP-complete and the knapsack problem for those not familiar. Thanks, Ryan Davis Acceleration.net Director of Programming Services 2831 NW 41st street, suite B Gainesville, FL 32606 Office: 352-335-6500 x 124 Fax: 352-335-6506 Larry Clapp wrote:
On Wed, Jul 11, 2007 at 04:07:53PM -0500, Ivan Salazar wrote:
OK, was this quiz a joke then? u_u
Well, I didn't propose it. I don't know what the guy who suggested it had in mind, one way or the other.
I initially thought it would be a hard problem (or at least take a long time to solve), thus my cautionary remarks, but the solution posted here earlier took ~0.001 seconds on my machine. I guess this dataset was sufficiently small. :)
-- L
_______________________________________________ quiz mailing list quiz@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/quiz
participants (3)
-
Ivan Salazar -
Larry Clapp -
Ryan Davis