Wednesday, 26 March 2014

Pseudo Code for KnapSack by using Greedy Method

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];
}

No comments:

Donate