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 big grin 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! wink

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.


When asked for a TWiki account, use your own or the default TWikiGuest account.



to top


You are here: Blog > BlogOnSoftware20060301

r1.5 - 29 Jan 2007 - 19:03 - ClausBrod to top

Blog
This site
RSS

  2017: 12 - 11 - 10
  2016: 10 - 7 - 3
  2015: 11 - 10 - 9 - 4 - 1
  2014: 5
  2013: 9 - 8 - 7 - 6 - 5
  2012: 2 - 10
  2011: 1 - 8 - 9 - 10 - 12
  2010: 11 - 10 - 9 - 4
  2009: 11 - 9 - 8 - 7 -
     6 - 5 - 4 - 3
  2008: 5 - 4 - 3 - 1
  2007: 12 - 8 - 7 - 6 -
     5 - 4 - 3 - 1
  2006: 4 - 3 - 2 - 1
  2005: 12 - 6 - 5 - 4
  2004: 12 - 11 - 10
  C++
  CoCreate Modeling
  COM & .NET
  Java
  Mac
  Lisp
  OpenSource
  Scripting
  Windows
  Stuff
Changes
Index
Search
Maintenance
Impressum
Datenschutzerklärung
Home



Jump:

Copyright © 1999-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback