%:-use_module(library(clpfd)).
%:-use_module(library(lists)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

campionario([2,4, 8,16,32,64,128,256,512,1024],
            [2,5,11,23,47,95,191,383,767,1535]).
            
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%
%%% NOTA: si possono prendere piu' istanze dello stesso item!!!!!!!!
%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

knapsack(Space,Profit) :-
    campionario(Weights,Costs),
    length(Weights,N),
    length(Vars,N),
    domain(Vars,0,Space), % Nota: ammesso anche 0
    %scalar_product(Weights,Vars,#=<,Space),
    %scalar_product(Costs,Vars,#>=,Profit),
    product(Weights,Vars,P1),    P1 #=< Space,
    product(Costs,Vars,P2),    P2 #>= Profit,    
    statistics(runtime,_),
    labeling([ff],Vars),!, %%%%%%%%%%%%%%%%%%%% <===
    statistics(runtime,[_,T]),
    write('Output in '),write(T),write(' ms'),nl, 
    write(Vars),nl.
knapsack(_,_) :-
    statistics(runtime,[_,T]),
    write('No solutions. Time: '),write(T),write(' ms'),nl.


product( [],[],0).
product([A|R],[B|S],C) :-
    product(R,S,C1),
    C #= A*B + C1.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
meta :-
    p(S,P), 
    write('Space='),write(S),write('\t Profit='),write(P),nl,
    knapsack(S,P),
    fail.   
            
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
%% RISULTATI SU 1.6GHz
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
%%    DATI SOPRA         %%%  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
%%  256, 373  yes  50ms      
%%  256, 374  no   50ms       
%%  512, 756  yes 581 ms     
%%  512, 757  no  581 ms     
%% 1024,1523  yes 13.1s      
%% 1024,1524  no  12.9s      
%% 2048,3058  yes 534.7s           
%% 2048,3059  no  563.9s                   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  


    
