% 使用模擬退火算法（SAA）解決0－1背包問題 

clear; 
w=[6 5 3 2 1 1]; %物品重量 
c=[61 59 31 21 15 5]; %物品價值 

M=10; % 背包總容量 

x=[0 0 0 0 0 0]; % 初始解 
[mm,n]=size(x); 
f=0; 
m=0; 
L=10*n; % Mapkob 鏈長 
for i=1:n 
f=f+c(i)*x(i); 
m=m+w(i)*x(i); 
end 

t0=200; % 控制參數t的初值 
t=t0; 
tf=0.9; % 
s0=0; 
s1=1; 
tic % 程序運行的初始,此處是為了計算程序運行的時間和程序結尾的toc對應 


while s0~=s1 % 產生新解 


flag=0; 
for k=1:L 
i=round(rand*(n-1))+1; 
if x(i)==0 
if m+w(i)<=M 
x(i)=1;f=f+c(i);flag=1; 
else 
j=round(rand*(n-1))+1; 
while x(j)==0 
j=round(rand*(n-1))+1; 
end 
df=c(i)-c(j);dm=w(i)-w(j); 
if m+dm<=M % 接受準則 
if (df>0)|(exp(df/t)>rand) 
x(i)=1;x(j)=0;f=f+df;m=m+dm;flag=1; 
end 
end 
end 
else 
j=round(rand*(n-1))+1; 
while x(j)==1 
j=round(rand*(n-1))+1; 
end 
df=c(j)-c(i);dm=w(j)-w(i); 
if m+dm<=M 
if (df>0)|(exp(df/t)>rand) 
x(i)=0;x(j)=1;f=f+df;m=m+dm;flag=1; 
end 
end 
end 
end 
t=t*tf; %衰減函數 
if flag==0 
s0=s0+1; 
else 
s0=0; 
end 
f_max=f; 
end 

f_max 
toc %程序運行的結尾，得出運行的時間