0-1背包问题是：有一个固定容量的背包，和固定种类的物品，每种物品只有一件。每件物品有各自的价值和重量，求解哪些物品放入背包可以使价值总和最大，且不超过背包容量。

本例中用分布估计算法求解0-1背包问题结果如下：

每代最优选择收益图

每代平均收益图

本例中的算例在下面下载：

0-1背包问题算例下载 people.sc.fsu.edu

0-1背包问题算例下载 本站

可以看到，分布估计算法可能在很靠前的迭代中就能得到很好的解，但是由于该算法不会保留上一代最优解，因此该解很可能丢失。从平均收益图来看，种群的整体收益平均值还是增加的。

主程序

主程序主要有以下四步：

for gen = 1:maxgen
    pop = makepop(popsize, stuffsize, p);               % 制作种群
    pop = capacitylimit(pop, capacity, weights, p);     % 限制重量
    spop = selection(pop, sn, profits);     % 选择优势个体
    p = makep(spop, p, alpha);              % 更新概率向量end

根据概率向量随机采样得到种群，并限制种群中个体的重量（不能超过背包容量），之后选择优势个体，并根据优势个体更新概率向量。进行下次迭代。

主程序如下：

function main()capacity = load("bag\P08\p08_c.txt");       % 背包容量bks = load("bag\P08\p08_s.txt");            % 最优解bks = bks';
weights = load("bag\P08\p08_w.txt");        % 重量weights = weights';
profits = load("bag\P08\p08_p.txt");        % 收益profits = profits';

popsize = 100;                  % 群体规模maxgen = 50;                    % 迭代次数stuffsize = length(weights);    % 物品数量p = ones(1, stuffsize) .* 0.5;  % 概率向量alpha = 1;                      % 学习速率sn = 0.7;                       % 优势个体数量sn = ceil(popsize * sn);

bestselection = zeros(maxgen, stuffsize);   % 记录每代最优选择avgweights = zeros(1, maxgen);              % 记录每代平均收益for gen = 1:maxgen
    pop = makepop(popsize, stuffsize, p);               % 制作种群
    pop = capacitylimit(pop, capacity, weights, p);     % 限制重量
    
    wgtsum = weightsum(pop, weights);
    [~, index] = max(wgtsum);
    bestselection(gen, :) = pop(index, :);
    avgweights(1, gen) = sum(wgtsum) / popsize;
    
    spop = selection(pop, sn, profits);     % 选择优势个体
    p = makep(spop, p, alpha);              % 更新概率向量endwgtsum = weightsum(bestselection, weights);
[~, index] = max(wgtsum);
figure(1);
plot(1:1:maxgen, wgtsum');
title("每代最优选择收益图");
figure(2);
plot(1:1:maxgen, avgweights);
title("每代平均收益图");end

制作种群函数

制作种群函数根据概率向量p进行随机采样，直至达到种群规模。概率向量p中的一项代表在该位置上取1的概率：

function pop = makepop(popsize, stuffsize, p)% 初始化种群，但没有限制重量% popsize       input  种群规模% stuffsize     input  物品数目% p             input  概率向量% pop           output 构造的种群pop = zeros(popsize, stuffsize);for i =1:popsize
    pop(i, :) = makepopv(stuffsize, p);endendfunction pop = makepopv(stuffsize, p)% 初始化个体，没有限制重量% stuffsize     input  物品数目% p             input  概率向量% pop           output 构造的个体tpop = rand(1, stuffsize);
pop = zeros(1, stuffsize);for j = 1:stuffsize    if tpop(1, j) <= p(1, j)
        pop(1, j) = 1;    endendend

限制重量函数

如果种群中某一个个体重量超过背包容量，则重新生成该个体：

function npop = capacitylimit(pop, capacity, weights, p)% 限制重量% pop           input  种群% capacity      input  背包容量% weights       input  重量% p             input  概率向量% npop          output 新种群npop = pop;
[popsize, stuffsize] = size(pop);for i = 1:popsize
    wgtsum = weightsumv(npop(i, :), weights);    while wgtsum > capacity
        npop(i, :) = makepopv(stuffsize, p);
        wgtsum = weightsumv(npop(i, :), weights);    endendend

选择优势个体函数

从种群中选择指定数量的优势个体：

function spop = selection(pop, sn, profits)% 选择% pop           input  种群% sn            input  选择数量% profits       input  收益向量% spop          output 选择的种群pftsum = profitssum(pop, profits);
pftsum = pftsum';
[~, index] = sort(pftsum, 'descend');
index = index(1: sn);
spop = pop(index, :);end

更新概率向量函数

该函数更新概率向量：

function np = makep(pop, p, alpha)% 更新概率向量% pop           input  种群% p             input  概率向量% alpha         input  学习速率% np            output 更新后的概率向量popsize = size(pop, 1);
np = (1 - alpha) .* p + alpha .* sum(pop) ./ popsize;

作者：mwangjs
链接：https://www.jianshu.com/p/37410b3ccd28