Knapsack Problems


Knapsack Problems: Algorithms and Computer Implementations
Martello & Toth

Submitter: I work in a college in [Canada] which has about 5000 full + part time students total. I found this gem while searching for wet books after a recent pipe leak. It’s a book on computer algorithms with a very helpful large floppy disk. I’m sure college students of today find this very useful. I guess they don’t know what they’re getting since it has never circulated since we got our new system in the early 2000s. Weed time!

Holly: I’m intrigued by the cover art. What does that have to do with algorithms and computers? The 5 1/4″ disk is pretty cool, though. And by cool, I mean awful.





  1. One could have a whole category of engineering/mathematical books with that specific Escher on the cover.

  2. Escher in general, and “Relativity” in particular, is a popular choice for illustrators to accompany stuff about recursion in computer science texts. (There’s even a Doctor Who story about recursion that’s named after an Escher print)

  3. It’s cited in the notes on the Wikipedia page for ‘Knapsack problem’ and B&N has “three new & used from $86.51.” While the pricing might be suspect, I hope you put it on a ‘free cart’ and didn’t bin it. (FWIW: I used to work in aerospace and volunteer at a Friends bookstore.)

    1. “What does [the cover] have to do with algorithms and computers?”

      Sorry about replying to my post. The cover if not by Escher is certainly Escheresque. I found the statement below after Googling “Escher algorithm”:

      “M C Escher (1898 to 1972) is a Dutch artist whose works are predominated by mathematical themes, many of which are purely algorithmic”

      Other links in the search are left as an exercise for the reader. Whether the cover is the best example of his algorithmic style is debatable.

      1. This came out in 1990. We were all super into Escher in the early to mid 1990. I remember people at school wearing shirts with his art on them. I still have a book of his art. (Library book sale find!)

  4. Knapsack problems are one of the more interesting subjects in conbinatorics. There are few good collections and expositions of them. Thus I’m not surprised, assuming that it’s any good, that it’s prices from $86 up on B&N. So I must wonder whether this toss is simply a matter of the librarian not knowing the subject area … though I must admit that I might look through it quickly and decide to toss it myself.
    My view on library acquisitions and deaccessions seems to be close to the reverse of the mainstream: I’d give circulation rate NO weight in accumulating a collection. Otherwise publilc library collecitions would (and do) follow the same premises as “pop culture”. My dear wife is the public librarian at the West Burke, Vermont library. She inherited a collection heavily weighed toward James Patterson and Danielle Steele. I’d toss all except for a couple of representative examples, and replace them with finer fiction (mystery, romance, and other). As long as circulation is a major criterion though, it won’t happen.

    1. Public libraries have a responsibility to provide the public with materials they want, and that means factoring in circulation. A shelf of materials that aren’t circulating is a waste of tax payer money regardless of how “fine” you think they are.

      1. I’d even say that if the book is valuable and doesn’t circulate, that’s just more evidence that it belongs in a specialized collection rather than a public library.

    2. There’s certainly a balancing point between the two. A good collection will make materials people didn’t realize they’d want easy to find as well as stock what people are asking for.

    1. And even if that weren’t the case, almost no one in any library’s customer base will have access to a 5 1/4-inch computer drive. I did my dissertation on such a drive, but that was in the mid-1980s. Technology has gone so far now that even finding CD drives in current computers is becoming more difficult. New Apple machines, for example, don’t have them. Keeping something like this in an ordinary library’s stock is thus rather like keeping a book written in, say, Aramaic.

      1. Based on the web version, even if the disk worked and you could find a reader, the sample code is in Fortran, which a very specialized-use language these days and not really appropriate for educational purposes.

        1. Yeah and “Art of Computer Programming” uses CISC Assembly, so let’s throw those out too.

  5. The book is available publicly as a PDF hosted at: (Università di Bologna РD.E.I.S. РOperations Research)

    I believe Escher was chosen as ‘Escherization,’ can probably be considered at least related to knapsack problems.

    Given a shape S, find a new shape T such that:
    T is as close as possible to S; and
    Copies of T fit together to form a tiling of the plane.

    In short, trying to fit images together, which when you think about it is a lot like optimizing the filling of a knapsack to maximize utility (the example the authors give in the preface).

  6. On one hand, this is a book on an evergreen topic in computer science, so the basic subject matter is definitely not obsolete. On the other hand, given that the topic is so evergreen, I guarantee you can find a newer book on the same topic which is probably more applicable to modern hardware and includes newer research.

    Oh, and Escher is on the cover because us computer science types think Escher is cool. That’s really the only excuse it has, or needs.

Comments are closed.