% 作者ID：lxwpp
% MATLAB源碼
% 使用模擬退火算法（SAA)解決0－1背包問題
% 林培科技制作完成 2004.10.26
% 同濟大學CS系模式識別
% w為物品的重量，c為物品的價值，M為背包的容量



clear;
tic

w=round(rand(1,1000)*100)+1;
c=round(rand(1,1000)*100)+1;



n=size(w,2);
x=zeros(1,n); %初始解

f=0;

M=0;
for i=1:n
M=M+w(i);
end;
M=round(M*0.8);
m=0;
L=10*n; % Mapkob 鏈長
for i=1:n
f=f+c(i)*x(i);
m=m+w(i)*x(i);
end

t0=500; % 控制參數t的初值
t=t0;
tf=0.95; %

e=0.00001;
%程序運行的初始,此處是為了計算程序運行的時間和程序結尾的toc對應



while t>e



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);m=m+w(i);
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;
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;
end
end
end
end
t=t*tf; %衰減函數

f_max=f;
end

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