% 使用模拟退火算法解决0-1背包问题
clear;
w=[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]; %物品价值
V=878; % 背包总容量
x=[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0];% 初始解
[m,n]=size(x);
tf=0.001;%截止温度
alpha=0.80;%退温系数
L=3*n; %the length of Markov chain 内循环次数
t0=200; % 控制参数t的初值
t=t0;
s=0; % 开始产生新解
h=1:L; B=[];
a=0;
while t>tf
for k=1:L
fval=x*c';
i=round(rand*(n-1))+1;
while x(i)==1
i=round(rand*(n-1))+1;
end
p=x;
p(i)=1;
fvolum_after=p*w';
if fvolum_after<=V
fval_after=p*c'
detval=fval_after-fval
if detval>0 %新解好于旧解
本内容试读结束,登录后可阅读更多
下载后可阅读完整内容,剩余2页未读,立即下载