%模擬退火解決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,20);                                            % 初始解
t0=2;                                                   %初始溫度
tf=0.1;                                                   %最終溫度 
t=t0;
alpha=0.05;
Lk=100*n;                                                 % Mapkob 鏈長 
f=0;
m=0;
for i=1:n,
    f=f+a(i)*x(i);
    m=m+c(i)*x(i);
end
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;
                    
                   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;
                
                end
            end
        end
    end
    t=t*alpha;
end
mmax=m;
mmax
end
toc