/* 

  Knapsack (unbounded) in Picat.

  http://rosettacode.org/wiki/Knapsack_problem/Unbounded
  """
  A traveller gets diverted and has to make an unscheduled stop in what 
  turns out to be Shangri La. Opting to leave, he is allowed to take as much 
  as he likes of the following items, so long as it will fit in his knapsack, 
  and he can carry it. He knows that he can carry no more than 25 'weights' in 
  total; and that the capacity of his knapsack is 0.25 'cubic lengths'.
  
  Looking just above the bar codes on the items he finds their weights and 
  volumes. He digs out his recent copy of a financial paper and gets the 
  value of each item.

  Item	                 Explanation	                Value (each)   weight	Volume (each)
  --------------------------------------------------------------------------------------------
  panacea (vials of)	Incredible healing properties	3000           0.3	0.025
  ichor (ampules of)	Vampires blood	                1800           0.2	0.015
  gold (bars)	        Shiney shiney	                2500           2.0	0.002
  Knapsack	        For the carrying of	        -              <= 25	<=0.25 

  He can only take whole units of any item, but there is much more of 
  any item than he could ever carry

  How many of each item does he take to maximise the value of items 
  he is carrying away with him?

  Note: There are four solutions that maximise the value taken. Only one need be given. 
  """


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

*/

import mip.

main => go.

go =>

  Value  = [3000.0, 1800.0, 2500.0  ],
  Weight = [   0.3,    0.2,    2.0  ],
  Volume = [   0.025,  0.015,  0.002],
  MaxWeight =  25.0,
  MaxVolume = 0.25,
  knapsack(Value,Weight,Volume,MaxWeight,MaxVolume, X,TotalValue,TotalWeight,TotalVolume),

  println(x=X),
  println(total_value=TotalValue),
  println(total_weight=TotalWeight),
  println(total_volume=TotalVolume),
  nl,
  
  nl.


knapsack(Value,Weight,Volume,MaxWeight,MaxVolume, X,TotalValue,TotalWeight,TotalVolume) => 
  N = Value.len,

  X = new_list(N),
  X :: 0..100000,

  TotalValue  #= sum([X[I]*Value[I]  : I in 1..N]),
  TotalWeight #= sum([X[I]*Weight[I] : I in 1..N]),
  TotalVolume #= sum([X[I]*Volume[I] : I in 1..N]),

  TotalWeight #<= MaxWeight,
  TotalVolume #<= MaxVolume,

  if var(TotalValue) then
    solve($[max(TotalValue)],X)
  else
    solve($[],X)
  end.