%模擬退火解決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

w=0;                                                     %  計算外循環迭代次數
while t>tf
    w=w+1;
    t=t*alpha;
end
mq=zeros(1,5);
for i=1:w    
    for p=1:Lk
      for q=1:5
        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
      mm(p)=m;                                         %  記錄某一溫度下的最優解
      xx(p,:)=x;
    end                                                 
       mj=0;
      for i=1:Lk                                      
        if mj<mm(i)
            mj=mm(i);
        end
      end
   mq(1:5)=mj;
end
mmax=0;
  for i=1:w                                            %  記錄全局最優解 
   if mmax<mq(i)
       mmax=mq(i);xper=xq(i,:)
   end
  end
mmax                                                   %  輸出全局最優解
xper                                                      %  輸出挑選結果
end