1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Knapsack problem

Discussion in 'C' started by arpit.jh001, Feb 15, 2012.

  1. arpit.jh001

    arpit.jh001 New Member

    Joined:
    Feb 15, 2012
    Messages:
    10
    Likes Received:
    0
    Trophy Points:
    0
    Code:
    #include<iostream.h>
    
    void print(float *a,int items)
    { float *temp=a;
      for(int r=0;r<items;r++)
      {  cout<<temp[r]<<"\t";
      }
      cout<<"\n";
    }
    void main()
    { int items,maxindex,W;
      float max=0.0,temp;
      float *w,*p;
      float *x,*pw;
      cout<<"Enter the number of items :";
      cin>>items;
      cout<<"\nEnter total size of Knapsack :";
      cin>>W;
      w = new float[items];
      p = new float[items];
      x = new float[items];
      pw = new float[items];
      cout<<"\n    Enter weight followed by profit on items \n";
      cout<<"       ---------------------------- \n";
      cout<<"        i       Weight      Profit          \n";
      cout<<"       ---------------------------- \n";
      for(int i=0;i<items;i++)
      {  cout<<"\t"<<(i+1)<<"\t";
          cin>>w[i];
          cin>>p[i];
      }
      for(int k=0;k<items;k++)
      {  pw[k]=(p[k]/w[k]);
          x[k]=0.0;
      }
      cout<<"\n p/w: ";
      print(pw,items);
      for(int j=0;j<items;j++)
      { for(int l=0;l<items;l++)
         { temp=pw[l];
            if(temp>max)
            { max=temp;
              maxindex=l;
            }
            else
            continue;
         }
        max=0.0;
         pw[maxindex]=0.0;
         if(w[maxindex]<=W)
         { x[maxindex] = 1.0;
            W = W-w[maxindex];
         }
         else
         { if(W!=0)
            { x[maxindex]=W/w[maxindex];
              W=0;
            }
            else
            x[maxindex]=0.0;
         }
      }
      cout<<"\n X :  " ;
      print(x,items);
    }
    
    /*can anyone suggest me a better solution than this*/
     
    Last edited by a moderator: Feb 15, 2012
  2. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England

Share This Page