/**
# A knapsack problem
The name *knapsack problem* derives from the following problem setting. We are given a number of objects that have
to be packed into a knapsack. Each object has a given value and a given size. The knapsack also has a given size,
so in general we cannot pack all objects into it. We want to pack the objects in such a way that we carry with us
the most valuable combination of objects, subject to the constraint that the total size of the objects does not
exceed the size of the knapsack. So we need to decide which objects are to be packed in the knapsack and which ones
are not. Knapsack problems can usually effectively be solved by means of the *branch-and-bound algorithm*.
*/

# Set of items
set I;

# Parameters
param a{I};
param b;
param c{I};

# Decision variables
var x{I} >= 0, <= 1;

# Objective
maximize z:
	sum {i in I} c[i] * x[i];
    
# Knapsack constraint
subject to knapsack:
	sum {i in I} a[i] * x[i] <= b;

data;

set I := 1 2 3 4 5;

param a := 
  1 5
  2 4
  3 7
  4 6
  5 2;
  
param b := 15;

param c := 
  1 5
  2 3
  3 6
  4 6
  5 2;
  
end;