knapsack.icn: Program to fill a container

August 8, 1993; Anthony V. Hewitt
This file is in the public domain.
This filter solves a knapsack problem - how to fill a container to
capacity by inserting items of various volumes.

 input:       a string of newline-separated volumes

 argument:    the capacity to be filled exactly

 output:      a single solution

It is derived from fillup.icn, which has a bewildering array of
options to make it applicable to real-world problems.  In
contrast, knapsack is merely a demonstration of the underlying
algorithm.

The return statement in trynext() greatly improves the efficiency
by restricting the search to fruitful branches of the search tree.
While the use of multiple returns may be considered poor style,
such a structure is often more readable than the alternatives.  In
this case, it also seems to be faster.

 Knapsack may be tested conveniently by piping to it the output
 of randi, a trivial program, like this:

 iconx randi 100 10 | iconx knapsack 250

 You may pick a different capacity, of course; this one just
 happens to produce a result quite quickly, as you might expect.

Source code | Program Library Page | Icon Home Page