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

topic end
<!--
   * Set TOPICTITLE = Claus Brod: Comment dit-on "knapsack" en français? (01 Mar 2006)
-->

<style type="text/css">
pre {background-color:#ffeecc;}
</style>

%STARTINCLUDE%
<a name="01"></a>
---+++ [[BlogOnSoftware20060301][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 [[http://en.wikipedia.org/wiki/Subset_sum_problem][subset sum problem]]
which is a special case of the 
[[http://www.nist.gov/dads/HTML/knapsackProblem.html][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 :D 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 
[[http://fr.wikipedia.org/wiki/Des_chiffres_et_des_lettres][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 [[OneSpaceModeling.MacroSubsetSum][subset sum algorithm in Lisp]].
I ran it both using CLISP and the implementation of Lisp provided in
[[OneSpaceModeling.WebHome][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 [[OneSpaceModeling.MacroSubsetSum][discussion of the algorithm]] for detailled results.

%COMMENT{type="below" nonotify="on"}%https://xkcd.com/287/

-- Main.ClausBrod - 01 Sep 2017



---

%STOPINCLUDE%
to top
End of topic
Skip to action links | Back to top
You are here: Blog > BlogOnSoftware20060301

r1.6 - 01 Sep 2017 - 15:30 - ClausBrod to top
Blog