Description
Actually there are lots of different
types of Knapsack problems, and here I'm
just describing one particular sort. See
the Wikipedia reference at the end of the
pages for more about the other types. 
The Knapsack Problem asks us to make a specific total
from a selection of numbers. For example, from these
numbers:
 23, 56, 45, 12, 78, 34, 73, 42, 4
make the total 172. It's not too bad when there are
only 10 or 15 numbers, but it rapidly becomes very
difficult, unless it happens to be easy!
Some collections of numbers make it easy. If each
number is more than the sum of all the preceeding
numbers, then it's easy. Likewise if there are lots
and lots of numbers of similar sizes, because then
you can get a good guess and fiddle around with it.
But there are cases for which there is no known fast
solution.
Wider setting
The Knapsack Problem is one of the NPcomplete problems.
In essence, the only known algorithms require examining
a large subset of possible solutions, and the number of
possible solutions is exponential.
Complexity Theory is a difficult area of mathematics,
and has widespread applications. See also the page on
P vs NP, where the ideas are starting to be expanded.
Further reading
To read more, here are a couple of references:
If you're interested in a more general, accessible
explanation, please let us know.
Contents
 
Links on this page
 
Site hosted by
Colin and
Rachel Wright:
 Maths, Design, Juggling, Computing,
 Embroidery, Proofreading,
 and other clever stuff.


Suggest a change ( <
What does this mean?) /
Send me email
Front Page /
All pages by date /
Site overview /
Top of page