%模擬退火解決0-1背包問題
clear;
a=[92,4,43,83,84,68,92,82,6,44,32,18,56,83,25,96,70,48,14,58];    %體積
c=[44,46,90,72,91,40,75,35,8,54,78,40,77,15,61,17,75,29,75,63];   %價值
n=length(a);
b=878;                                                   %  背包容量
x=zeros(1,n);                                            %  初始解
t0=20;                                                   %  初始溫度
tf=0.5;                                                  %  最終溫度 
t=t0;
alpha=0.5;                                               %  衰減系數 
Lk=100*n;                                                %  馬氏鏈長 
f=0;
m=0;
for i=1:n
    f=f+a(i)*x(i);                                       %  總體積
    m=m+c(i)*x(i);                                       %  總價值
end
fmax=f;
mmax=m;
xper=x;
ii=0;

while t>tf;
    for p=1:Lk;
        i=round(rand*(n-1))+1;
        if x(i)==0;
            if f+a(i)<=b;
                x(i)=1;m=m+c(i);f=f+a(i);
            else f+a(i)>b;
                j=round(rand*(n-1))+1;
                while x(j)==0;
                    j=round(rand*(n-1))+1;
                end
                da=a(i)-a(j);
                dc=c(i)-c(j);
                if f+da<=b                             %  接受準則 
                    if dc>0
                    x(i)=1;x(j)=0;f=f+da;m=m+dc;
                    else exp(dc/t)>rand; 
                    x(i)=1;x(j)=0;f=f+da;m=m+dc;
                   end
                end
            end
        else x(i)==1;
            j=round(rand*(n-1))+1;
            while x(j)==1;
                j=round(rand*(n-1))+1;
            end
            da=a(j)-a(i);
            dc=c(j)-c(i);
            if f+da<=b                                 %  接受準則 
                if dc>0
                    x(i)=0;x(j)=1;f=f+da;m=m+dc;
                else exp(dc/t)>rand;
                    x(i)=0;x(j)=1;f=f+da;m=m+dc;
                end
            end
        end
     
      if mmax<m
          mmax=m;fmax=f;xper=x;
      end
      
    end
       
     ii=ii+1;
    t=t*alpha;                %   降溫
     mq(ii)=mmax;             % 記錄局部最優
     fq(ii)=fmax;
end
mmax=0;
  for i=1:ii ;                                        
   if mmax<mq(i);            %  記錄全局最大價值 
       mmax=mq(i);                                    
   end
   if fmax<fq(i)  ;          %  記錄背包用量                             
       fmax=mq(i);
  end
end
mmax                         %  輸出全局最優解      
fmax                         %  輸出此時背包容量
xper                         %  輸出物品選擇情況
end