KNAPSACK PROBLEM

KNAPSACK PROBLEM

#include”iostream.h”
#include”conio.h”
#include”process.h”
int Capacity;
int profit[40],weight[40],n;
float ratio[40],temp[40],temp1[40],soln[40];
class knapsack
{
public:
void getdata();
void sort();
void display();
void calculatesoln();
float getmaxprofit();
};

void knapsack::getdata()
{
clrscr();
cout<<"\nEnter the Capacity of Bag\n";
cin>>Capacity;
//cout< cout<<"Enter the number of objects\n";
cin>>n;
//cout< cout<<"Enter the profit\n\n";
for(int i=0;i cin>>profit[i];
cout< cout<<"Enter the weight\n\n";
for(i=0;i cin>>weight[i];
cout< for(i=0;i {
ratio[i]=(float)profit[i]/(float)weight[i];
temp[i]=ratio[i];
temp1[i]=ratio[i];
}
}

void knapsack::sort()
{
float t;
for(int i=0;i {
for(int j=i+1;j {
if(ratio[i] {
t=ratio[i];
ratio[i]=ratio[j];
ratio[j]=t;
}
}
}
}

void knapsack::calculatesoln()
{
int maxcapac=0;
for(int i=0;i {
for(int p=0;p if(temp[p]==ratio[i])
{
if((maxcapac+weight[p])<=Capacity)
{
soln[p]=1.0;
maxcapac+=weight[p];
temp[p]=-1.0;
}
/* else
{
soln[p]=(float)(Capacity-maxcapac)/weight[p];
maxcapac+=Capacity-maxcapac;
temp[p]=-1.0;
}*/
break;
}
if(maxcapac==Capacity)
break;
}
}


float knapsack::getmaxprofit()
{
knapsack k;
float maxprofit=0.0;
k.calculatesoln();
k.display();
for(int i=0;i maxprofit+=(soln[i]*profit[i]);
return maxprofit;
}

void knapsack::display()
{
clrscr();
cout<<"\nKNAPSACK PROBLEM\n";
cout<<"----------------";
cout<<"\nWeight of each Node\n";
for(int i=0;i cout< cout<<"\n";
cout<<"\nProfit of each node\n";
for(i=0;i cout< cout<<"\n";
cout<<"\n\n Profit Ratio Pi/Wi is\n\n";
for(i=0;i cout< cout<<"\nValues \tProfit/Weight\n";
for(i=0;i {
cout<<"\nx"< }
}

void main()
{
clrscr();
knapsack kp;
kp.getdata();
kp.sort();
cout<<"\n\nMaximum Profit="< getch();
}














OUTPUT:

KNAPSACK PROBLEM

Enter the Capacity of Bag
10
Enter the number of objects
5
Enter the profit
80
60
75
20
10
0
Enter the weight
2
1
5
2
2

KNAPSACK PROBLEM

Weight of each Node
2 1 5 2 2

Profit of each node
80 60 75 20 10

Profit Ratio Pi/Wi is

60 40 15 10 5

Values Profit/Weight
x0 1 40
x1 1 60
x2 1 15
x3 1 10
x4 0 5

Maximum Profit=235