/* 

  Knapsack in Picat.

  Port of B-Prolog program
  http://www.probp.com/examples/tabling/knapsack.pl
  """
  Taken from "Simplifying Dynamic Programming via Mode-directed Tabling"
  Software Practice and Experience, 38(1): 75-94, 2008, by Hai-Feng Guo, Gopal Gupta
  """

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

*/


% import util.
% import cp.


main => go.

go =>
   statistics(_, _),
   knapsack([50, 10, 400, 30, 30, 20, 10, 5, 30, 20,
       6, 20, 20, 30, 9, 30, 20, 500, 20, 40,
      30, 8, 3, 5, 9, 200, 10, 400, 20, 30,
      50, 10, 400, 30, 30, 20, 10, 5, 30, 20,
       6, 20, 20, 30, 9, 30, 20, 500, 20, 40,
       6, 20, 20, 30, 9, 30, 20, 500, 20, 40,
      30, 8, 3, 5, 9, 200, 10, 400, 20, 30,
      50, 10, 400, 30, 30, 20, 10, 5, 30, 20,
       6, 20, 20, 30, 9, 30, 20, 500, 20, 40,
      30, 8, 3, 5, 9, 200, 10, 400, 20, 30], 4000, V),
   statistics(_, [_, B]),
   print("There is a solution for this knapsack problem"), nl,
   print('The maximal number of items is '), print(V), nl,
   print('execution time = '), print(B), print(' ms'), nl.


table(+, +, max)
knapsack(_, Z1, Z2) ?=> Z1=0, Z1=Z2.
knapsack(FL, K, V) ?=>
    FL=[_ | L],
    knapsack(L, K, V).
knapsack(FL, K, V) =>
    FL = [F | L],
    K1 = K - F,
    K1 >= 0,
    knapsack(L, K1, V1),
    V = V1 + 1.