/* 

  Simple knapsack problem in Picat.

  Problem from http://sourceforge.net/forum/forum.php?thread_id=1432186&forum_id=335511
  """
  Knapsack maximization problem example
  @author Fernando Lopez Hernandez (f.lopezATuamDOTes)

  In this problem a thief have a knapsack with capacity of 10 units.
  He could charge the knapsack with golden ingots of size 4, silver ingots
  of size 3, and bronze ingots of size 2. Each ingot value is 15, 12 and 7
  respectively.

  The solver goal is to find a solution who maximize profit with the above
  restrictions. That is to say: If G represents the number of golden ingots,
  S the number of silver ingots, B the number of bronze ingots,
  and P the profit, we define the following constraints:
  4G + 3S + 2B <= 10
  15G + 12S + 7B = P

  Solution:
  [ 1, 2, 0 ]
  i.e. 1 Gold, 2 Silver and 0 Bronze
  """

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


import cp.


main => go.


go =>
  values(Values),
  weights(Weights),
  weight_max(WeightMax),

  N = Values.length,

  % decision variables
  X = new_list(N),
  % X :: 0..100,

  foreach(I in 1..N) X[I] #>= 0 end,

  knapsack(Weights, Values, X, WeightMax,Profit),

  solve($[max(Profit)], X),

  println(x=X),
  println(profit=Profit),
  
  nl.

% data
weight_max(WeightMax) => WeightMax= 10.

% Gold, Silver, Bronze        
values(Values) => Values = [15, 12, 7].
weights(Weights) => Weights = [4, 3, 2].

%
% knapsack: 
%  given Weights and Values
%  - ensure that the total weights <= WeightMax
%  - calculate the profit (which will be maximized)
%
knapsack(Weights, Values,Take, WeightMax,Profit) =>
   sum([W*T : {W,T} in zip(Weights, Take)]) #=< WeightMax,
   Profit #= sum([V*T : {V,T} in zip(Values,Take)]).