$TITLE  KNAPSACK PROBLEM
$OFFUPPER
* We solve a simple knapsack problem
*
*  References: 
*              V. Chvatal, Linear Programming
*

  SETS
       I   knapsack constraint /KNAPSACK/
       J   packages   / P1 * P4 / ;

  PARAMETERS

  C(J)  return or pleasure from jth package
   /P1   4
    P2   5
    P3   5
    P4   2 /

  B(I)  limiting size of knapsack
   /KNAPSACK 120 /

  A(J)  package sizes
   /P1   33
    P2   49
    P3   51
    P4   22 /;


  VARIABLES
       X(J) 0 or 1 indicating if the package is chosen
       Z       total return ;

  BINARY VARIABLE X ;

  EQUATIONS
       COST        define objective function
       LIMIT(I)  knapsack limit  ;

  COST ..        Z  =E=  SUM( J, C(J)*X(J) ) ;

LIMIT(I) ..   SUM(J, A(J)*X(J) ) =L= B(I) ;


  MODEL  KNAPSACK /ALL/ ;

  SOLVE KNAPSACK USING MIP MAXIMIZING Z ;

  DISPLAY X.L, X.M   ;