#

#
Knapsack Problem

#
Dennis Shasha

#
Omniheurist Course

#
Computer Science

##
*
Description
*

This is a warm-up to the ambulance problem.
The idea is to use a genetic algorithm on a simple problem.
(Note that there are good polynomial approximations to this
problem that you might look up.)

Problem statement: given a collection of items each having
a weight and value and a knapsack with a certain weight capacity,
find a subset of the items whose total weight is less than
the capacity and whose total value is maximized.

The data will be in the form:

item(weight, value), where there will be 1000 data items.

Here is some typical data.
Total capacity for this simplified case is 1250.
.
You will have 3 minutes of user time.