greedy.m

一个贪婪算法的仿真程序

function [sch,tolval,tolwei]=backpack(maxwei,weight,value)
n=size(weight,2);
sch=zeros(1,n);
p=value./weight;
[a,b]=sort(p);%a从小到大排序后的向量,b是对应元素原始下标
b=b(n:-1:1);tw=0;%已装入背包的物品重量
for i=1:n
    if (tw+weight(b(i)))<=maxwei
        tw=tw+weight(b(i));
        sch(b(i))=1;
    end
end
tolwei=tw;
tolval=sum(value(find(sch)));