A list,

In the 0-1 knapsack example, suppose you have 12 items, quality of 2 pounds respectively, 5 pounds, 18 pounds, 3 pounds, 2 pounds, 5 pounds, ten pounds, 4 pounds, 11 pounds, 7 pounds, 14 pounds, 6 pounds, worth 5 yuan, 10 yuan, 13 yuan respectively, 4 yuan, three yuan, 11 yuan, 13 yuan, 10 yuan, 8 yuan, 16 yuan, 7 yuan, 4 yuan, The maximum allowable mass of the bag is 46 pounds.

Ii. Source code

clear
clc
a = 0.95;
k = [5;10;13;4;3;11;13;10;8;16;7;4]; % value k = -k; % simulated annealing algorithm is to solve the minimum value, so the negative value d = [2;5;18;3;2;5;10;4;11;7;14;6]; % quality restriction =44;
num = 12;
sol_new = ones(1,num); E_current = INF; E_best = inf; %E_new is the new solution. %E_best is the optimal solution sol_current = sol_new; sol_best = sol_new; t0 =97;
tf = 3;
t = t0;
p = 1;

while t >= tf
    for r = 1:100% produces a random disturbance TMP =ceil(rand*num);
        sol_new(1,tmp) = ~sol_new(1,tmp); % checks whether the constraint is metwhile 1
            q = (sol_new * d <= restriction);
            if~q p = ~p; % implement the first one with staggered reversal heads and tails1
                tmp = find(sol_new == 1);
                if p
                    sol_new(1,tmp(1)) = 0;
                else
                    sol_new(1,tmp(end)) = 0;
                end
            else
                breakE_new = sol_new * k;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
Copy the code

3. Operation results

Fourth, note

Version: 2014 a