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