%模擬退火解決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;
tic
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
      ii=ii+1;
      if mmax<m
          mmax=m;fmax=f;xper=x;
      end
      
    end
       

    t=t*alpha;
     mq(ii)=mmax;
end
mmax=0;
  for i=1:ii                                         %  記錄全局最優解 
   if mmax<mq(i)
       mmax=mq(i);
   end
  end
mmax          %  輸出全局最優解      
xper
end
toc