The Knapsack Problem

Some resources about knapsack problem; Note: Knapsack can be approximated in ways that Travelling Salesperson cannot; variants;

The Knapsack Game: Any number can play... (the more people the more paralytical...)

• Each student is assigned a number (make it easy - an integer, say the last two digits of your social security number).
• We need to find a collection of students whose number will sum to exactly 200 (or whatever).

How do you start?

Once you have "put" a given number into the knapsack, can you be sure that assignment is reliable?

Version of 3 November 2003