Knapsack Problem

Dennis Shasha

Omniheurist Course

Computer Science



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.