二维优化问题——背包问题_如何求解二维背包问题

背包问题要求从 n 个物品中选取若干装入一个背包中。每个物品有体积(vi>0)和价值(pi)，每个箱子有体积限制()。目标是寻找最优的将物品分配到背包的方案，使每个背包中物品的体积之和不超过容积限制，而价值最大。

(1)

(2)

式中，xi＝1表示物品i被装入箱子，xi=0则表示物品i未被选中。

从下面物品中选取若干，在总体积不超过1000情况下使总价值最大。

遗传编码考虑为长度为50，表示某个物品是否被选中，变异交叉可正常进行。

%v=profit
v=xlsread('H:\original\profit_and_weight.xlsx','sheet1','A1:A50');
V0=1500;
%种群大小
popsize=4;
%二进制编码长度
chromlength=50;
%交叉概率
pc = 0.3;
%变异概率
pm = 0.001;
%初始种群
pop = initpop(popsize,chromlength);
hanshuzhi=zeros(100,1);
% [bestindividual,bestfit] = best(pop,fitvalue);
%  hanshuzhi(1)=bestfit;
for i = 1:100
    %计算适应度值（函数值）
    [objvalue,newpop1] = cal_objvalue(pop,V0,v);
    fitvalue = objvalue;
    %选择操作
    newpop = selection(newpop1,fitvalue);
    %交叉操作
    newpop = crossover(newpop,pc);
    %变异操作
    newpop = mutation(newpop,pm);
    %寻找最优解
    [bestindividual,bestfit] = best(pop,fitvalue);
    hanshuzhi(i)=bestfit;
    %更新种群 
    t=1;
    for j=1:popsize
        if fitvalue(j)==bestfit
            newpop(t)=pop(j);
            t=t+1;
        end
    end
    pop = newpop;
    
    
if i==100
number=1:50;
lastindividual=number(bestindividual==1);
end
end
extra_space=ones(100,1);
for i=1:100
    extra_space(i)=V0-hanshuzhi(i);
end
fprintf('The best individual is --->>%2f\n');
lastindividual
fprintf('The best value is --->>%5.2f\n',min(extra_space));
figure
plot(extra_space(:),'k');