Drop Down MenusCSS Drop Down MenuPure CSS Dropdown Menu

0/1 Knapsack Problem


Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[]
such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0-1 property).

Source Code:

#include<iostream.h>
#include<conio.h>


void knapsack(float*,float*,float,float);
void  main()
{ clrscr();
  float value[50],weight[50],max,i,n;
  cout<<"Program for 0/1 knapsack by-Tarun Rawat \n\n";
  cout<<"Enter the maximum capacity of knapsack: ";
  cin>>max;
  cout<<"Enter the number of item: ";
  cin>>n;
  cout<<"Enter the values of item,according to per unit value in descending order:\n";
  for( i=0;i<n;i++)
  {cin>>value[i];
  }
  cout<<"Enter the values of weight according to value of item:\n";
   for( i=0;i<n;i++)
  {cin>>weight[i];
  }
  cout<<"Elements enter by you is \n";
  for( i=0;i<n;i++)
  {cout<<"\nvalue "<<value[i]<<" weight "<<weight[i];
  }
  knapsack(value,weight,max,n);
getch();
}

void knapsack(float value[],float weight[],float max,float n)
  { float current=0,i,rem;
    float currentval=0;
     for(i=0;i<n;i++)
     { if((current<=max)&& (weight[i]<=max-current))
       {    current=current+weight[i];
        currentval=currentval+value[i];
        }
     }
     rem=max-current;
   cout<<"\n\nmaximum profit is: "<<currentval;
   cout<<"\ncurrent weight is: "<<current;
   cout<<"\nweight left: "<<rem;
  }

No comments:

Post a Comment

Blogger Widgets

Find Us On Google, Just type - way2cplusplus -

If you have any questions on implementing or understanding this C++ Program , shoot me a comment and I'll be glad to help! :) :)