These fields are all optional and need only be supplied if you would like a direct reply. Subject Your email address Your real name

You must answer this! If you don't, my spam filtering will ensure that I never see your email. What's 8 plus five (in digits only)?

Please make your changes here and then
Editing tips and layout rules.
File: KnapsackProblem !! Description [[[>50 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 NP-complete 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 wide-spread applications. See also the page on PvsNP, where the ideas are starting to be expanded. ---- !! Further reading To read more, here are a couple of references: * http://en.wikipedia.org/wiki/Knapsack_problem * http://en.wikipedia.org/wiki/NP-complete * http://xkcd.com/287/ If you're interested in a more general, accessible explanation, please letusknow.