1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | % % ECLiPSe SAMPLE CODE % Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/ % % Bounded-Knapsack problem from % Pack 0 or more items of each type, obeying the knapsack weight constraint. % There is a limited supply of each item type. % % Using ic as a finite-domain solver. % % Sample run: % % % eclipse -f knapsack_cp.ecl -e main % Found a solution with cost -635 % ... % Found a solution with cost -1010 % Found no solution with cost -1849.0 .. -1011.0 % 1 of map % 1 of compass % 1 of water % 2 of glucose % 3 of banana % 1 of cheese % 1 of suntan cream % 1 of waterproof overclothes % 1 of note-case % 1 of sunglasses % 1 of socks % weight = 396 ; value = 1010 % :- lib(ic). :- lib(branch_and_bound). model( Weights , Values , Bounds , Capacity , Amounts , Weight , Value ) :- ( foreach ( Bound , Bounds ), foreach ( Amount , Amounts ) do Amount $:: 0.. Bound ), integers( Amounts ), Amounts * Weights $= Weight , Weight $=< Capacity , Amounts * Values $= Value . solve( Weights , Values , Bounds , Capacity , Amounts , Weight , Value ) :- model( Weights , Values , Bounds , Capacity , Amounts , Weight , Value ), Cost #= - Value , minimize (search( Amounts , 0, largest, indomain_reverse_split, complete, []), Cost ). main :- data( Names , Weights , Values , Bounds , Capacity ), solve( Weights , Values , Bounds , Capacity , Amounts , Weight , Value ), ( foreach ( Amount , Amounts ), foreach ( Name , Names ) do ( Amount >0 -> printf( "%d of %w%n" , [ Amount , Name ]) ; true ) ), writeln(weight= Weight ;value= Value ). % data(Names, Weights, Values, Bounds, Capacity) data( [map,compass,water,sandwich,glucose,tin,banana,apple,cheese,beer, 'suntan cream' ,camera, 't-shirt' ,trousers,umbrella, 'waterproof trousers' , 'waterproof overclothes' , 'note-case' ,sunglasses,towel,socks,book], [ 9,13,153, 50,15,68,27,39,23,52,11,32,24,48,73,42,43,22, 7,18, 4,30], [150,35,200, 60,60,45,60,40,30,10,70,30,15,10,40,70,75,80,20,12,50,10], [ 1, 1, 2, 2, 2, 3, 3, 3, 1, 3, 1, 1, 2, 2, 1, 1, 1, 1, 1, 2, 1, 2], 400 ). |