Packages
fixpoint
0.7.2
0.22.2
0.22.1
0.21.5
0.21.4
0.21.3
0.21.2
0.21.1
0.21.0
0.20.6
0.20.5
0.20.4
0.20.3
0.20.2
0.20.1
0.19.5
0.19.4
0.19.3
0.19.2
0.19.1
0.18.2
0.18.1
0.17.6
0.17.5
0.17.4
0.17.3
0.17.2
0.17.1
0.16.5
0.16.4
0.16.3
0.16.2
0.16.1
0.16.0
0.15.6
0.15.5
0.15.4
0.15.3
0.15.2
0.15.1
0.15.0
0.14.9
0.14.8
0.14.7
0.14.6
0.14.5
0.14.4
0.14.3
0.14.2
0.14.1
0.13.5
0.13.4
0.13.2
0.13.1
0.12.9
0.12.8
0.12.7
0.12.6
0.12.5
0.12.4
0.12.2
0.12.1
0.11.8
0.11.7
0.11.6
0.11.5
0.11.4
0.11.3
0.11.2
0.11.1
0.10.7
0.10.6
0.10.5
0.10.4
0.10.3
0.10.2
0.10.1
0.9.12
0.9.11
0.9.10
0.9.9
0.9.8
0.9.7
0.9.6
0.9.5
0.9.4
0.9.3
0.9.2
0.9.1
0.9.0
0.8.52
0.8.51
0.8.50
0.8.49
0.8.48
0.8.46
0.8.44
0.8.43
0.8.42
0.8.41
0.8.40
0.8.39
0.8.38
0.8.37
0.8.36
0.8.35
0.8.34
0.8.33
0.8.32
0.8.31
0.8.30
0.8.29
0.8.28
0.8.27
0.8.26
0.8.25
0.8.24
0.8.23
0.8.22
0.8.21
0.8.20
0.8.19
0.8.18
0.8.17
0.8.16
0.8.15
0.8.14
0.8.13
0.8.12
0.8.11
0.8.10
0.8.9
0.8.8
0.8.7
0.8.6
0.8.5
0.8.4
0.8.3
0.8.2
0.8.1
0.8.0
0.7.10
0.7.9
0.7.8
0.7.7
0.7.6
0.7.5
0.7.4
0.7.3
0.7.2
0.7.1
0.7.0
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.12
0.5.11
0.5.10
0.5.9
0.5.8
0.5.7
0.5.6
0.5.5
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.3
0.4.2
0.4.1
0.4.0
0.3.6
0.3.5
0.3.4
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.1.3
0.1.2
0.1.1
0.1.0
Constraint Programming Solver
Current section
Files
Jump to
Current section
Files
data/knapsack/minizinc/knapsack.mzn
% Use this editor as a MiniZinc scratch book
%
% Knapsack problem/0-1 in MiniZinc.
%
% From Rosetta code:
% http://rosettacode.org/wiki/Knapsack_problem/0-1
% """
% A tourist wants to make a good trip at the weekend with his friends. They
% will go to the mountains to see the wonders of nature, so he needs to
% pack well for the trip. He has a good knapsack for carrying things, but
% knows that he can carry a maximum of only 4kg in it and it will have
% to last the whole day. He creates a list of what he wants to bring for the
% trip but the total weight of all items is too much. He then decides to
% add columns to his initial list detailing their weights and a numerical
% value representing how important the item is for the trip.
%
% Here is the list:
% Table of potential knapsack items
% item weight (dag) value
% map 9 150
% compass 13 35
% water 153 200
% sandwich 50 160
% glucose 15 60
% tin 68 45
% banana 27 60
% apple 39 40
% cheese 23 30
% beer 52 10
% suntan cream 11 70
% camera 32 30
% T-shirt 24 15
% trousers 48 10
% umbrella 73 40
% waterproof trousers 42 70
% waterproof overclothes 43 75
% note-case 22 80
% sunglasses 7 20
% towel 18 12
% socks 4 50
% book 30 10
% knapsack <=400 dag ?
%
% The tourist can choose to take any combination of items from the list, but
% only one of each item is available. He may not cut or diminish the items,
% so he can only take whole units of any item.
%
% Which items does the tourist carry in his knapsack so that their total weight
% does not exceed 400 dag [4 kg], and their total value is maximised?
%
% [dag = decagram = 10 grams]
% """
%
%
% This MiniZinc model was created by Hakan Kjellerstrand, hakank@bonetmail.com
% See also my MiniZinc page: http://www.hakank.org/minizinc/
%
% include "globals.mzn";
int: num_items = 22;
array[1..num_items, 1..2] of int: items;
array[1..num_items] of string: items_str;
% decision variables
array[1..num_items] of var 0..1: x;
var int: total_weight = sum(i in 1..num_items) ( x[i]*items[i,1] );
var int: total_value = sum(i in 1..num_items) ( x[i]*items[i,2] );
solve :: int_search(
x,
input_order,
indomain_min,
complete)
maximize total_value;
% satisfy;
constraint
total_weight <= 400
% /\ total_value = 1030 % testing all optimal solutions
;
% output
% [
% "total_value: " ++ show(total_value) ++ "\n" ++
% "total_weight: " ++ show(total_weight) ++ "\n"
% ] ++
% [
% if fix(x[i]) > 0 then
% show(items_str[i]) ++ ": " ++ show(x[i]) ++ " value: " ++ show(items[i,2]) ++ "\n"
% else
% ""
% endif
% | i in 1..num_items
% ]
% ++ ["\n"]
% ;
%
% Data
%
items_str =
[
"map","compass","water","sandwich","glucose","tin","banana","apple","cheese",
"beer","suntancream","camera","T-shirt","trousers","umbrella","waterproof trousers",
"waterproof overclothes","note-case","sunglasses","towel","socks","book"];
%
% weight (dag) (each) value (each) pieces(s)
%
items = array2d(1..num_items, 1..2, [
9, 150,
13, 35,
153, 200,
50, 160,
15, 60,
68, 45,
27, 60,
39, 40,
23, 30,
52, 10,
11, 70,
32, 30,
24, 15,
48, 10,
73, 40,
42, 70,
43, 75,
22, 80,
7, 20,
18, 12,
4, 50,
30, 10
]);