function [sBest,valBest]=SA_knapsack(Tmax,Tmin,lambda)
// Call: [sBest,valBest]=SA_knapsack(10000,0.001,0.5) 
// Tmax = initial value of the temperature
// Tmin = final value of the temperature
// lambda = parameter used in the penalty function (weight of the value component)

// input data
v=[92,57,59,68,60,43,67,84,87,72];//[3,4,1,5,2];  // values of the objects
w=[23,31,29,44,53,38,63,85,89,82];//[10,8,3,6,5]; // weights of the objects 
c=165;//20;           // knapsack capacity

// optimal solution [1,1,1,1,0,1,0,0,0,0]
n=size(v,2);
s=init(n);      // initial solution
val=value(v,w,c,s);
sBest=s;        // best solution find so far
valBest=val;
T=Tmax;         // temperature initialization
k=0
while T>Tmin
    k=k+1
    sNew=transform(s);          // new candidate solution
    valNew=value(v,w,c,sNew);...// value of the new candidate
    disp(valNew,'val=');
    a=accept(val,valNew,T);     // decision on acceptance
    if a==1
        s=sNew;
        val=valNew;
    end
    if val>valBest
        sBest=s;    
        valBest=val;
    end;    
    T=T*0.9995;                // cooling schedule
//    T=Tmax/k;
end    
endfunction
// random initial solution
function s=init(n)
    s=grand(1,n,"uin",0,1);   // random selection of objects
endfunction 

//evaluation
function val=value(v,w,c,s)
     wKnapsack=w*s';          // total weight
     vKnapsack=v*s';          // total value
     if wKnapsack<=c 
         val=vKnapsack;       // the selected objects fit into the knapsack
     else
         val=lambda*vKnapsack+(1-lambda)*(c-wKnapsack);
     end           
endfunction    

// random perturbation
function sNew=transform(s)
n=length(s);
sNew=s;
i=grand(1,1,"uin",1,n); 
sNew(i)=1-s(i)
endfunction

// acceptance function
// a=1 - the new tour is accepted
// a=0 - the new tour is not accepted
function a=accept(val,valNew,T)
if valNew>val
    a=1;
else
    p=exp((valNew-val)/T);
    if grand(1,1,"unf",0,1)<p
        a=1;
    else
        a=0;
    end
end    
endfunction

[sBest,valBest]=SA_knapsack(10000,0.001,0.5)

