#include
#include
const int MAX=30;
int mfk(int,int);
int max(int,int);
int profit[MAX];
int weight[MAX];
int v[MAX][MAX];
int n;
int M;
void main()
{
int j;
int optsol;
clrscr();
cout<<"\n KNAPSACK PROBLEM";
cout<<"\nenter the no. of objects:";
cin>>n;
cout<<"enter the weight OF THE OBJECT ONE BY ONE ::";
for(int i=1;i<=n;i++)
{
cout<<"\n";
cout<<"[";
cout< cout<<"] :: " ;
cin>>weight[i];
}
cout<<"enter the profit one by one :: ";
for(i=1;i<=n;i++)
{
cout<<"\n";
cout<<"[";
cout< cout<<"] :: " ;
cin>>profit[i];
}
cout<<"enter the total knapsack capacity:";
cin>>M;
for(i=0;i<=M;i++)
v[0][i]=0;
for(i=0;i<=n;i++)
v[i][0]=0;
for(i=1;i<=n;i++)
for(j=1;j<=M;j++)
v[i][j]=-1;
cout< optsol=mfk(n,M);
cout<<"optimal sol::"< getch();
}
int mfk(int i,int j)
{
int p;
if(v[i][j]==-1)
{
if(j p=mfk(i-1,j);
else
p=max(mfk(i-1,j),mfk(i-1,j-weight[i])+profit[i]);
v[i][j]=p;
}
return v[i][j];
}
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
|
No feedbacks found. Be the first to respond and make money from revenue sharing program.
|