/* 

  Generalized Knapsack problem in Picat.

  From 
  http://www.math.ohiou.edu/~vardges/math443/homeworks/homework1.doc
  http://74.125.77.132/search?q=cache:gvXFEnS7aN4J:www.math.ohiou.edu/~vardges/math443/homew
orks/homework1.doc+%22generalized+knapsack+problem%22&cd=36&hl=en&ct=clnk&gl=se
  """
  Problem 3. Generalized knapsack problem.

  Suppose that Tom is going on an overnight hike. There are 3 different items Tom is 
  considering taking along the trip. Tom's knapsack can hold up to 20 lbs of items. 
  The weight of item i is w[i]. Tom might take at most L[i] copies of item i.  
  The benefit Tom feels he would get from taking k copies of item i is b[i,k]. 
  The values of w[i], L[i] and b[i,k] are listed in the following table. 

  item weight(lbs) max # of copies Benefit
  i    w[i] L[i]                   b[i,1] b[i,2] b[i,3] b[i,4]
  1    4    3                      45     70     90  
  2    5    3                      20     40     50  
  3    3    4                      50     70     85      95

  Formulate an integer program whose solution will tell Tom how to maximize the 
  total profit. 

  Hint: Note that b[i,k] is not a linear function on k, and that complicates the problem. 
  To overcome this difficulty, introduce the following decision variables. For each item i 
  (i=1,2,3) and possible number of copies k (k=1,...,L[i]): 
  """



  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 ?=>
  N = 3,
  MaxWeight = 20,

  Weight = [4,5,3],
  Limits = [3,3,4],
  MaxLimits = max(Limits),

  Benefits =  [
           [45,70,90,0],
           [20,40,50,0],
           [50,70,85,95]
           ],

  % decision variables
  X = new_list(N),
  X :: 1..MaxLimits,
  
  generalized_knapsack(Weight,Limits,MaxWeight,Benefits, TotWeight,TotBenefit,X),

  Vars = X ++ [TotBenefit,TotWeight],
  solve($[max(TotBenefit)],Vars),

  println(x=X),
  println(totBenefit=TotBenefit),
  println(totWeight=TotWeight),
  
  nl.

go => true.



generalized_knapsack(Weight,Limits,MaxWeight,Benefits, TotWeight,TotBenefit,X) =>
  N = X.len,
  % total benefits
  TotBenefit #= sum([B : I in 1..N, matrix_element(Benefits,I,X[I],B)]),
  % satisfy the limits for each item
  foreach(I in 1..N) 
    X[I] #<= Limits[I]
  end,
  
  % total weight
  TotWeight #= sum([X[I]*Weight[I] : I in 1..N]),
  TotWeight #<= MaxWeight.