News for hackers. Stuff that matters.
Re:Genetic Algorithm for Knapsack Problem by scubbo on Wednesday June 19, 2013 @08:02AM (#5905004)
Nitpicking, I know, but I think the author has misinterpreted the XKCD strip. IMO, " - as fast as possible, of course. Want something on the Travelling Salesman?" is not a continuation of the client's request (Give me set of appetizers, fulfilling these requirements, as quickly as possible), but rather a response to the waiter ("I have to see to these other tables" - "and you have to do so as quickly as possible"). This makes the mention of "Travelling Salesman" more appropriate (since it deals with optimizing travel time for certain visits).

Am I misinterpreting the dialogue?

(Not that it matters, of course!)

Re:Genetic Algorithm for Knapsack Problem by raverbashing on Wednesday June 19, 2013 @09:46AM (#5905469)
Every NP problem can be converted in another NP problem, so you could probably try to convert your subset problem to a TSP problem (but it wouldn't be useful in practice)
Re:Genetic Algorithm for Knapsack Problem by a-nikolaev on Wednesday June 19, 2013 @11:19AM (#5906020)
Nitpicking: In general, an NP problem can be reduced to an NP-hard problem (in poly-time).
Re:Genetic Algorithm for Knapsack Problem by javajosh on Wednesday June 19, 2013 @11:12AM (#5905980)
No, you're not misinterpreting. The character is drawn holding a bunch of papers, and he's apparently offering a paper on Traveling Salesman to be "helpful" to the waiter who has 6 tables to visit "as fast as possible".

So, in a way, this entire solution is the product of an error in reproduction. :)

Re:Genetic Algorithm for Knapsack Problem by jasallen on Wednesday June 19, 2013 @08:46AM (#5905160)
Huh, I didn't get that, but I think you're right. deep :-)
Re:Genetic Algorithm for Knapsack Problem by grinnbearit on Wednesday June 19, 2013 @09:10AM (#5905285)
You're right, its actually the sum of subsets problem