| 1 |
/*** |
| 2 |
!Test |
| 3 |
expected: |
| 4 |
- !Result |
| 5 |
solution: !Solution |
| 6 |
objective: 17 |
| 7 |
x: [0, 1, 0, 1, 1] |
| 8 |
***/ |
| 9 |
|
| 10 |
%------------------------------------------------------------------------------% |
| 11 |
% The classical 0/1 multidimensional knapsack problem. |
| 12 |
% |
| 13 |
% There is a knapsack with m different capacity constraints and n items with |
| 14 |
% profits and weights. The goal is to maximise the total profit of the items |
| 15 |
% in the knapsack while not violating any of the capacity constraints. |
| 16 |
%------------------------------------------------------------------------------% |
| 17 |
|
| 18 |
int: n; |
| 19 |
int: m; |
| 20 |
|
| 21 |
array[1..n] of int: Profits; |
| 22 |
array[1..n,1..m] of int: Weights; |
| 23 |
array[1..m] of int: Capacities; |
| 24 |
|
| 25 |
array[1..n] of var 0..1: x; |
| 26 |
|
| 27 |
constraint |
| 28 |
forall(i in 1..m) ( |
| 29 |
sum([Weights[j,i] * x[j] | j in 1..n]) <= Capacities[i] |
| 30 |
); |
| 31 |
|
| 32 |
solve maximize |
| 33 |
sum([x[j] * Profits[j] | j in 1..n]); |
| 34 |
|
| 35 |
output [ "multidimknapsack_simple " ] ++ |
| 36 |
[ show(x[i]) ++ if i = n then "\n" else " " endif | i in 1..n ]; |
| 37 |
|
| 38 |
%------------------------------------------------------------------------------% |
| 39 |
% data |
| 40 |
|
| 41 |
n = 5; |
| 42 |
m = 3; |
| 43 |
|
| 44 |
Profits = [5,6,3,7,4]; |
| 45 |
|
| 46 |
Capacities = [5,10,15]; |
| 47 |
|
| 48 |
Weights = [| 2, 3, 2 |
| 49 |
| 1, 4, 4 |
| 50 |
| 1, 2, 5 |
| 51 |
| 3, 2, 3 |
| 52 |
| 1, 3, 5 |]; |
| 53 |
|