Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
2.4 kB · 78 lines
at develop
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879%------------------------------------------------------------------------------%% Multi Dimensional Knapsack Problem%------------------------------------------------------------------------------%include "knapsack.mzn";%------------------------------------------------------------------------------%% Parametersint: N; % number of variablesint: M; % number of constraintsset of int: VRange = 1..N;set of int: CRange = 1..M;array[CRange,VRange] of int: a; % Weight of items per binarray[CRange] of int: b; % Sizes of binsarray[VRange] of int: c; % Profit of items%------------------------------------------------------------------------------%% Ignored parametersint: z; % Normally the optimal value%------------------------------------------------------------------------------%% Variablesarray[VRange] of var 0..1: x; % Whether an item is packedarray[CRange] of var 0..ub_array(b): bVar; % Total weight in a binvar 0..sum(c): objective;constraint objective = sum(i in VRange)(c[i] * x[i]); % Total profit%------------------------------------------------------------------------------%% Constraints % Constraining the size of the bins %constraint forall(i in CRange)( bVar[i] >= 0 /\ bVar[i] <= b[i] ); % Knapsack constraints %constraint forall(i in CRange)( knapsack([a[i,j] | j in VRange], c, x, bVar[i], z) ); %------------------------------------------------------------------------------%% Some integrety check for the (input) dataconstraint forall(i in CRange,j in VRange)( assert(a[i,j] >= 0, "negative values in a") );constraint forall(i in CRange)( assert(b[i] >= 0, "negative values in b") );constraint forall(j in VRange)( assert(c[j] >= 0, "negative values in c") );constraint assert(z >= 0, "negative z");%------------------------------------------------------------------------------%% Searchsolve :: int_search(x, input_order, indomain_max, complete) maximize objective;%------------------------------------------------------------------------------%% Outputoutput [ "x = ", show(x), ";\n", "objective = ", show(objective), ";\n"];%------------------------------------------------------------------------------%