Comment dit-on "knapsack" en français? (01 Mar 2006)

This week, a customer of our software asked a seemingly innocent question; given a set of tools of various lengths, he wanted to find subsets of those tools which, when combined, can be used to manufacture a screw of a given length.

From the description, I deduced that we were talking about a variation of the subset sum problem which is a special case of the knapsack problem. Faint memories of my time at university arose; I couldn't resist the weird intellectual tickle. Or maybe it was just the beginning of my pollen allergy for this year Anyway, I searched high and low on my quest to reacquire long-lost knowledge.

One of the weirder search results was a TV show called Des chiffres et des lettres which has been running for ages now on French TV. In that show, they play a game called "Le compte est bon" which is actually a variation of the subset sum problem! The candidates are supposed to solve this puzzle in about a minute or so during the show. Wow - these French guys must be math geniuses!

Anyway, I couldn't help but try a subset sum algorithm in Lisp^?. I ran it both using CLISP and the implementation of Lisp provided in CoCreate OneSpace Modeling^?. I started to collect some benchmark results for CLISP, comparing interpreted and compiled code to get a better feeling for the kind of improvements I can expect from the CLISP compiler. In the case of CLISP, the compiler improves runtime by roughly an order of magnitude. See the discussion of the algorithm^? for detailled results.

to top