knapsack - résout un problème du sac à dos 0-1 multiple
knapsack résout un problème du sac à dos 0-1 multiple avec n (n >= 2) objets et m sacs à dos (m >= 1). profit est le vecteur des profits (entiers) des n objets et weight est le vecteur des poids correspondants (entiers). capa est le vecteur des capacités (entières) des m sacs à dos. bck est un entier optionnel : le nombre maximum de backtrackings à effectuer, si une solution heuristique est exigée. Si la solution exacte est exigée bck peut être omis ou avoir une valeur négative. earn est la valeur du critère pour la solution "optimale" et ind est un vecteur donnant les positions optimales : ind(i) donne le numéro du sac à dos où l'objet i est mis et cette valeur est 0 si l'objet i n'est pas dans la solution optimale.
Rappelons que le problème à résoudre est le suivant : p(i) et w désignent respectivement le profit et le poids de l'objet i 1=1,...,n; c(j) désigne la capacité du sac à dos j j=1,...,m; q(j,i) désigne la quantité d'objets i dans le sac à dos j (en fait 0 ou 1).
On cherche à maximiser le profit global E : E=p(1)*[x(1,1)+...+x(m,1)]+...+p(n)*[x(1,n)+...+x(m,n)]
sous les contraintes : [w(1)*x(j,1)+...+w(n)*x(j,m)] <= c(j) ; j=1,...,m [x(1,i)+...+x(m,i)] <= 1 ; i=1,...,n x(j,i)= 0 ou 1 p(),w(),c() sont des entiers positifs.
weight=ones(1,15).*.[1:4]; profit=ones(1,60); capa=[15 45 30 60]; [earn,ind]=knapsack(profit,weight,capa)
qassign ,