%% ======================================================== %% Auteur: Jean-Michel Richer %% email: jean-michel.richer@univ-angers.fr %% ======================================================== %% %% Problème du sac à dos : %% %% Etant donné un ensemble d'objets pesant un certain %% poids (weight) et apportant un certain profit (profit) %% on cherche à trouver quels objets mettre dans le sac %% à dos de manière à obtenir le profit maximum tout en %% ne dépassant pas le contrainte de poids maximal (W_max) %% %% ======================================================== include "globals.mzn"; %% -------------------------- %% Variables %% -------------------------- % maximum number of articles int: N = 10; % maximum weight int: W_max = 269; array[1..N] of int: profit; array[1..N] of int: weight; array[1..N] of var 0..1: x; profit = [55,10,47,5,4,50,8,61,85,87] ; weight = [95,4,60,32,23,72,80,62,65,46] ; %% -------------------------- %% Constraints %% -------------------------- constraint sum(i in 1..N)(weight[i] * x[i]) <= W_max; %% -------------------------- %% Search %% -------------------------- var int: gain = sum(i in 1..N)(profit[i] * x[i]); solve :: int_search(x, max_regret,indomain_split, complete) maximize gain; %% -------------------------- %% Result %% -------------------------- output ["x = ", show(x), " ", show(gain)];