Trading

• Suppose you're outfitting a trade ship

• There is a list of merchandise you could put on it

        @items = ('Precious jewelery', 'Gold nugget', ...,
                  'Egg-sized emerald');

• Each item has a size and a value:

        %size  = ('Egg-sized emerald' => 11, 'Gold nugget' => 5, ...);
        %value = ('Egg-sized emerald' => 30, 'Gold nugget' => 12, ...);

• The ship's hold can only accomodate some of the items:

        $MAX_SIZE  = 100;

• It costs a certain amount to send the ship at all:

        $BUDGET    = 300;

• Question: is there a cargo that makes the trip worth while?

• This is called the knapsack problem

Next

Copyright © 2005 M. J. Dominus