模拟退火背包问题求解

    clear;
    clc;
    %物品价值
    earn=[5;10;13;4;3;11;13;10;8;16;7;4];
    earn=-earn;%模拟退火算法求解最小值，故取负数
    cost=[2;5;18;3;2;5;10;4;11;7;14;6];
    num=12;
    restriction=46;%包最大允许质量
    sol_new=ones(1,num);
    sol_current=sol_new;
    sol_best=sol_new;
    E_current=inf;
    E_best=inf;
    t0=97;
    tf=3;
    t=t0;
    p=1;
    a=0.95;
    while t>tf
    for i=1:1000
        %产生随机扰动
        temp=ceil(rand*12);
        sol_new(1:temp)=~sol_new(1:temp);
        %约束条件判断
        while sol_new*cost>restriction
            %随机找到一个1逆转为0
            temp=find(sol_new==1);
            %if p
            %    sol_new(1,temp(1))=0;
            %   p=~p;
            %else
             %   sol_new(1,temp(end))=0;
              %  p=~p;
            %end
            temp1=ceil(rand*size(temp));
            sol_new(1,temp(temp1))=0;
        end
    
        E_new=sol_new*earn;
        if E_new<E_current
            E_current=E_new;
            sol_current=sol_new;
            if E_new<E_best
                E_best=E_new;
                sol_best=sol_new;
            end
        else
            if rand<exp(-(E_new-E_current)/t)
                E_current=E_new;
                sol_current=sol_new;
            else
                sol_new=sol_current;
            end
        end
    end
    t=t*a;
    end
    
    disp('最优解为：')
    disp(sol_best);
    disp('物品总价值')
    val=-E_best;
    disp(val);
    disp('背包重量物品总重量')
    disp(sol_best*cost)