greedy.txt

使用贪婪算法 解决0－1背包问题MATLAB源代码

使用贪婪算法解决0－1背包问题MATLAB程序代码

%  使用贪婪算法解决0－1背包问题
%  作者：林培科技  同济大学CS系
%  时间：2004.10.30 


clear;
tic


w=round(rand(1,1000)*100)+1;    %物品重量        
c=round(rand(1,1000)*100)+1;     %物品价值


n=size(w,2);                        ％问题规模
f=0;

M=0;
for i=1:n
  M=M+w(i);
end;
M=round(M*0.8);


h=n;

for i=1:n
    r(i)=c(i)/w(i);
    flag(i)=0;
end
w=w';
c=c';
r=r';
flag=flag';
p=[w c r flag];
pp=sortrows(p,3);
pp=pp';

space=M;

while pp(1,h)<=space
    f=f+pp(2,h);
    pp(4,h)=1;
    space=space-pp(1,h);
    h=h-1;
    if h==n+1
        break;
    end
end


f_max_greedy=f
toc