function [sBest,vBest,wBest]=TS_knapsack(TLsize, iterMax)
// Exemplu apel: [sBest,valBest]=TS_knapsack(10) 
// TLsize = lungimea liste cu configuratii tabu
// iterMax = numar maxim de iteratii

// definirea problemei
v=[3,4,1,5,2];   // valorile obiectelor
w=[10,8,3,6,5];  // dimensiunile obiectelor
c=20;            // capacitatea rucsacului
n=size(v,2);
// solutia initiala
s=init(n);
[vTotal,wTotal]=valoare(v,w,s);
sBest=s;    // cea mai buna solutie gasita pana in momentul curent
vBest=vTotal;
wBest=wTotal;
TSlist=[];     // initializarea listei de configuratii interzise
iter=1;
stop=0;
while (iter<=iterMax) and (stop==0)
    [sNew,TSlist]=transform(s,TSlist,TLsize);
    [vTotalNew,wTotalNew]=valoare(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
    else
        stop=1    
    end
    iter=iter+1;
end    
endfunction
// solutie initiala = selectie aleatoare
function s=init(n)
    s=grand(1,n,"uin",0,1);
endfunction 

//calcul functie obiectiv
function [vTotal,wTotal]=valoare(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

// perturbare aleatoare simpla (includerea sau excluderea unui obiect)
function [sNew,TSlistNew]=transform(s,TSlist,TLsize)
n=length(s);
sLocalBest=s;
TSlistNew=TSlist;
[vLocalBest,wLocalBest]=valoare(v,w,s);
for i=1:n
    sNew=s;
    sNew(i)=1-s(i);
    if tabuCheck(sNew,TSlist)==0 then
        [vNew,wNew]=valoare(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,50)
