function [sBest,vBest,wBest]=TS_knapsack(TLsize, iterMax)
// Call: [sBest,valBest]=TS_knapsack(10) 
// TLsize = maximal length of the tabu list
// iterMax = maximal number of iterations

// input data
// 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);
// initial solution
s=init(n);
[vTotal,wTotal]=value(v,w,s);
sBest=s;    // best solution found so far
vBest=vTotal;
wBest=wTotal;
TSlist=[];     // initialization of the tabu list
iter=1;
stop=0;
while (iter<=iterMax) //& (stop==0)
    [sNew,TSlist]=transform(s,TSlist,TLsize);
    [vTotalNew,wTotalNew]=value(v,w,sNew);
    disp(iter,'iter=');
    disp(vTotalNew,'val=');
    disp(wTotalNew,'w=');
    disp(sNew,'s=');
    disp(TSlist,'TSlist=');
    //if better(vTotalNew,wTotalNew,vTotal,wTotal,c)==1
    s=sNew;
    vTotal=vTotalNew;
    wTotal=wTotalNew;
    if better(vTotalNew,wTotalNew,vBest,wBest,c)==1 then
            sBest=s;
            vBest=vTotal;
            wBest=wTotal;
    end
    iter=iter+1;
end    
endfunction
// initial random solution
function s=init(n)
    s=grand(1,n,"uin",0,1);
endfunction 

//computation of the value and weight 
function [vTotal,wTotal]=value(v,w,s)
     wTotal=w*s';
     vTotal=v*s';        
endfunction    

function result=tabuCheck(s,TSlist)
    m=size(TSlist,1);
    result=0
    i=1
    while (result==0)&(i<=m)
        if s==TSlist(i,:) then
            result=1
        else
            i=i+1    
        end
    end
endfunction

function result=better(vNew,wNew,vLocalBest,wLocalBest,c)
    result=0;
    if (wNew<=c)&(wLocalBest<=c) then
        if(vNew>vLocalBest) then 
            result=1;
        end
     elseif (wNew<=c)&(wLocalBest>c) then
         result=1
     elseif (wNew<wLocalBest) then
         result=1
    end
endfunction

// simple random perturbation
function [sLocalBest,TSlistNew]=transform(s,TSlist,TLsize)
n=length(s);
sLocalBest=s;
TSlistNew=TSlist;
[vLocalBest,wLocalBest]=value(v,w,s);
for i=1:n
    sNew=s;
    sNew(i)=1-s(i);
    if tabuCheck(sNew,TSlist)==0 then
        [vNew,wNew]=value(v,w,sNew);
        if better(vNew,wNew,vLocalBest,wLocalBest,c)==1 then
            sLocalBest=sNew;
            vLocalBest=vNew;
            wLocalBest=wNew;
        end  
    end
end
if size(TSlistNew,1)>=TLsize then
    TSlistNew(1,:)=[]
end
if tabuCheck(sLocalBest,TSlist)==0 then
    TSlistNew=[TSlistNew;sLocalBest]
end    
endfunction

[sBest,vBest,wBest]=TS_knapsack(5,1000)
