/* 

  Knapsack (unbounded) integer version 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 is an integer (CP/SAT) version of the var float version version 
  knapsack_rosetta_code_unbounded.pi
  As usual we multiply the float by some value to get integers.

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

*/

import cp.

main => go.

go =>

  Value  = [3000, 1800, 2500 ],
  Weight = [   3,    2,   20 ], % multiply by 10
  Volume = [  25,   15,    2],  % multiply by 1000
  MaxWeight = 250, % multiply by 10
  MaxVolume = 250, % multiply by 1000
  knapsack(Value,Weight,Volume,MaxWeight,MaxVolume, X,TotalValue,TotalWeight,TotalVolume),

  println(x=X),
  println(total_value=TotalValue),
  println(total_weight=(TotalWeight/10.0)), % and then divide to get the proper scale
  println(total_volume=(TotalVolume/1000.0)),
  nl,
  
  nl.

/* 

  Found optimal value: 54500
  Now looking for all optimal solutions.
  x = [0,15,11]
  total_value = 54500
  total_weight = 25.0
  total_volume = 0.247

  x = [3,10,11]
  total_value = 54500
  total_weight = 24.899999999999999
  total_volume = 0.247

  x = [6,5,11]
  total_value = 54500
  total_weight = 24.800000000000001
  total_volume = 0.247

  x = [9,0,11]
  total_value = 54500
  total_weight = 24.699999999999999
  total_volume = 0.247

*/
go2 =>

  Value  = [3000, 1800, 2500 ],
  Weight = [   3,    2,   20 ], % mult by 10
  Volume = [  25,   15,    2], % mult by 1000
  MaxWeight = 250, % mult by 10
  MaxVolume = 250, % mult by 1000
  knapsack(Value,Weight,Volume,MaxWeight,MaxVolume, _X,TotalValue,_TotalWeight,_TotalVolume),

  printf("Found optimal value: %d\nNow looking for all optimal solutions.\n", TotalValue),

  knapsack(Value,Weight,Volume,MaxWeight,MaxVolume, X,TotalValue,TotalWeight,TotalVolume), 

  println(x=X),
  println(total_value=TotalValue),
  println(total_weight=(TotalWeight/10.0)),
  println(total_volume=(TotalVolume/1000.0)),
  nl,
  fail,
  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,

  Vars = X ++ [TotalValue,TotalWeight,TotalVolume],
  if var(TotalValue) then
    solve($[max(TotalValue)],Vars)
  else
    solve($[],Vars)
  end.