In the knapsack model, one wants to select items to place into a knapsack to maximize a measure of utility without exceeding the capacity of the knapsack. This model can be generalized to many other areas such as truck loading, bin packing, choosing science experiments for the Space Shuttle, and so on. An in-depth description of this model can be found in Using Variable Domain Functions.

SETS:

  ITEMS / ANT_REPEL, BEER, BLANKET,

   BRATWURST, BROWNIES, FRISBEE, SALAD,

    WATERMELON/:

     INCLUDE, WEIGHT, RATING;

ENDSETS

 

DATA:

  WEIGHT RATING =

    1      2

    3      9

    4      3

    3      8

    3     10

    1      6

    5      4

   10     10;

  KNAPSACK_CAPACITY = 15;

ENDDATA

 

MAX = @SUM( ITEMS: RATING * INCLUDE);

 

@SUM( ITEMS: WEIGHT * INCLUDE) <=

KNAPSACK_CAPACITY;

 

@FOR( ITEMS: @BIN( INCLUDE));

Model: KNAPSACK