knapsack — solves a 0-1 multiple knapsack problem
[earn,ind] = knapsack(profit,weight,capa,[bck])
integer row vector
integer row vector
integer row vector
integer
integer
integer row vector
The 0-1 multiple knapsack problem with n (n >= 2) items and m knapsacks (m >= 1) is defined as follow:
Maximize the global profit E=profit*sum(X,1) under the constraints:
X*weight <= capa
sum(X,1) <= 1 ; i=1,...,n
X(j,i)= 0 or 1
Where
is the vector of the "profits" of the n items. The entries must be positive integers.
is the vector of the corresponding "weights". The entries must be positive integers.
is the vector of the (integer) capacities of the m knapsacks.The entries must be positive integers.
is a m by n
matrix.
est une matrice m par n à valeurs dans {0,1}.
[earn,ind] = knapsack(profit,weight,capa) solves
the problem. It returns in
the value of the criterium E for
the "optimal" solution if it has been found. In case of error, earn is assigned to a negative value:
means that a knapsack cannot contain any item.
means that an item cannot fit into any knapsack.
means that a knapsack contains all the items.
the integer vector of the knapsack number where item
i is inserted and this value is 0 if the
item i is not in the optimal solution. The matrix
X can be derived from
ind by
items=1:n;
items(ind==0)==[];
ind(ind==0)=[];
X=sparse([ind;items]',ones(n,1),[m,n])
is an optional integer: the maximum number of
backtrackings to be performed if heuristic solution is
required. If the exact solution is required
bck must be omitted or assigned to a
negative value.
weight=ones(1,15).*.[1:4]; profit=ones(1,60); capa=[15 40 30 60]; [earn,ind]=knapsack(profit,weight,capa) items=1:60; items(ind==0)=[]; ind(ind==0)=[]; X=full(sparse([ind;items]',ones(ind),[4,60])) //one row per sacks X*weight' //sack weights x=sum(X,1); and(x<=1) //contraints check profit*x'==earn