Algorithm GreedyKnapSack(m,n)
//P[1:n] and w[1:n] contain the
//profitand weights respectively of the n objects
//ordered such that p[i]/w[i] >= p[i+1]/w[i+1]
// mis the KnapSack size and x[1:n] is the soln. vector
{
for i:= to n do
x[i]:=0.0;
U:=m;
for i:=1 to n do
{
if(w[i]>U)then
break;
x[i]:=1.0;
U:=U-w[i];
}
if(i<=n)then
x[i]:=U/w[i];
}
//P[1:n] and w[1:n] contain the
//profitand weights respectively of the n objects
//ordered such that p[i]/w[i] >= p[i+1]/w[i+1]
// mis the KnapSack size and x[1:n] is the soln. vector
{
for i:= to n do
x[i]:=0.0;
U:=m;
for i:=1 to n do
{
if(w[i]>U)then
break;
x[i]:=1.0;
U:=U-w[i];
}
if(i<=n)then
x[i]:=U/w[i];
}
No comments:
Post a Comment