/*

  Number of days problem (knapsack) Picat.

  From Nathan Brixius
  "Solving a Knapsack problem with Solver Foundation and LINQ"
  http://blogs.msdn.com/natbr/archive/2010/05/06/solving-a-knapsack-problem-with-solver-foundation-and-linq.aspx
 """
  Let's say I have this list of days and prices:

    List<ReservationPrice> prices = new List<ReservationPrice>(); 
    prices.Add(new ReservationPrice { NumberOfDays = 1, Price = 1000 }); 
    prices.Add(new ReservationPrice { NumberOfDays = 2, Price = 1200 }); 
    prices.Add(new ReservationPrice { NumberOfDays = 3, Price = 2500 }); 
    prices.Add(new ReservationPrice { NumberOfDays = 4, Price = 3100 }); 
    prices.Add(new ReservationPrice { NumberOfDays = 7, Price = 4000 }); 

  What I would like to able to do now is: give me the best price 
  from the list based on a number of days.

  So if ask for 3 days the best price from the list is from child one 
  (1000) and two (1200), but there are of course different combinations. 
  How would an algorithm that found the best price from this list 
  look like ?
  """


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

*/

import cp.


main => go.

go =>

   % days(Days),
   % cost(Costs),
   data(Data),
   Days1 = [],
   Costs1 = [],
   foreach([Day,Cost] in Data) 
      Days1 := Days1 ++ [Day],
      Costs1 := Costs1 ++ [Cost]
   end, 
   Days = Days1,
   Costs = Costs1,

   writeln(days=Days),
   writeln(costs=Costs),
  
   MaxDays = sum(Days),
   writeln(maxDays=MaxDays),

   % Calculate the best deal for all days from 1..17
   foreach(D in 1..MaxDays)
      number_of_days(Days,Costs,D,X,TotalCost),
      writeln(num_days=D),
      writeln(x=X),
      writeln(total_cost=TotalCost),
      nl
   end.
        
scalar_product(A, X, Product) => 
   Product #= sum([S : I in 1..A.length, S #= A[I]*X[I]]).


number_of_days(Days,Costs,NumDays,X,TotalCost) =>

   MaxDays #= sum(Days),
   MaxCost #= sum(Costs),
   Days :: 1..MaxDays,
   TotalCost :: 1..MaxCost,
   Len = length(Days),

   X = new_list(Len),
   X :: 0..1,
   scalar_product(Days,X,NumDays),
   scalar_product(Costs,X,TotalCost),

   solve([$min(TotalCost)], X).
         

data(Data) => 
  Data = [[1,1000],
          [2,1200],
          [3,2500],
          [4,3100],
          [7,4000]].

% Number of days, Cost
days(Days) => Days = [1,2,3,4,7].
cost(Cost) => Cost = [1000,1200,2500,3100,4000].