Re: set based guru's help wanted

From: --CELKO-- (jcelko212_at_earthlink.net)
Date: 12/12/04 

Date: 12 Dec 2004 12:31:46 -0800

>> refer to a book you can neither name nor find nor quote from. <<

KNAPSACK PROBLEMS by Silvano Martello & Paolo Toth. 1991, John Wiley &
Sons, 296 pages; ISBN 0-471-92420-2. And it is soooo out of print. I
found an old book review I wrote on it and not the actual book that is
buried in my garage.

This book is part of Wiley's Discrete Mathematics & Optimization Series
edited by Ronald Graham -- a name everyone should know. It came with a
diskette which has the major algorithms in the text on it.

The knapsack problem comes in many versions, but theclassic one which
gives it that name involves packing a knapsack for a trip. You can
carry only a certain load. Each item which you can put into the sack
has a weight and a profit to you. The idea is to maximize the total
value of the knapsack by careful packing without breaking your back.

The mathematics in the book is bit heavy for the average programmer,
but nothing which cannot be read. I feel that the text should have
been supplemented with some artwork or graphics to make it a bit easier
to understand. The lack of actual examples in the beginning is also a
bad point.

The algorithms are the meat of any book on this topic and this is where
the book falls apart. This book has a diskette with the algorithms
written in FORTRAN 66! Who has a PC version of FORTRAN 66 on their
machine? People wrote in in 'C' or Pascal back then. The authors seem
to know that they made a bad choice because all their algorithms in the
text are in pseudo-Pascal with mathematical notations mixed in.

But ignoring all of that, their FORTRAN code stinks. It is a pile of
spaghetti code with bad formatting. I spent four hours trying to hand
translate some of the FORTRAN into Pascal. It was incredibly painful
and yielded a program which is almost as unclear as the original.

At that point, I went on to other things and lost interest in napsack
and bin packing problems. I have no idea if another book of algorithms
was ever done; nothign but research papers show up on Amazon.

Relevant Pages

  • Re: set based gurus help wanted
    ... >This book is part of Wiley's Discrete Mathematics & Optimization Series ... >diskette which has the major algorithms in the text on it. ... >gives it that name involves packing a knapsack for a trip. ... >value of the knapsack by careful packing without breaking your back. ...
    (microsoft.public.sqlserver.programming)
  • Re: sorting dates
    ... The idea is to have them in a format that sortcan use without any further modification and that doesn't require a comparison function. ... Whether they are strings or numbers will likely make very little difference in the OP's case as whatever operations are done to the table rows will likely take far, far longer than the actual sort. ... I'm also weighing in the algorithms I have worked out for myself. ... date format (packing integers is a "time-honored programming tradition") -- been around for considerably longer than JavaScript. ...
    (comp.lang.javascript)
  • Re: OT - people v computer
    ... written long ago by a very smart guy- cool algorithms and such, ... but completely unreadable, it was Fortran, used named blocks (which ... and purposely used the overlapping blocks ... of the ugly fortran and be asked to find the bug. ...
    (comp.lang.tcl)
  • Re: C++ for combinatorial optimization problems
    ... just a header providing access to their Fortran library. ... arbitrary algorithms in all Turing-complete programming languages. ... question is how much support you get and how easy the algorithms are ...
    (comp.lang.cpp)
  • Re: What Algorithims are used for IEEE Mathematical and Inquiry Intrinsic Procedures
    ... There were stories about the extended precision functions ... they went more toward the usual polynomial algorithms. ... in some of the patents. ... It might be that the Fortran version hasn't been scanned yet. ...
    (comp.lang.fortran)