#include <stdlib>
#include <iostream>
#include <iomanip.h>
//using namespace std;
int p_no[50],n,m,mtot=0;
int w[50],p[50],x[5];
float d[50];//,x[50];
template <class T>
void sort(T *a,int i,int j)
{ T temp;
temp=a[j];
a[j]=a[i];
a[i]=temp;
return;
}
void display()
{
cout<<"\nBrng\t\tW\t\tP\t\tP/W\n";
for(int i=0;i<n;i++)
cout<<p_no[i]<<"\t\t"<<w[i]<<"\t\t"<<p[i]<<"\t\t"<<setprecision(2)<<d[i]<<"\n";
}
void knapsack()
{
int u,i;
u=m;
int x[50];
for(i=0;i<n;i++)
x[i]=0;
for(i=0;i<n;i++)
{
if(w[i]>u){
//break;
x[i]=0;}
else
{
x[i]=1;
u=u-w[i];
}
}
int opt_solution=0;
for(i=0;i<n;i++)
{
//cout<<x[i]<<" ";
opt_solution=opt_solution+(p[i]*x[i]);
}
cout<<"\n\n========= Greedy By Density (1 : dimasukkan, 0 : tidak dimasukkan)===========\n";
cout<<"\nBrng\t\tW\t\tP\t\tP/W\t\tGreedy Density\n";
for(int i=0;i<n;i++)
cout<<p_no[i]<<"\t\t"<<w[i]<<"\t\t"<<p[i]<<"\t\t"<<setprecision(2)<<d[i]<<"\t\t"<<x[i]<<"\n";
mtot=m-u;
cout<<"\n\nTotal Berat\t: "<<mtot;
cout<<"\nTotal profit\t: "<<opt_solution;
}
int main(int argc, char *argv[])
{
int i;
cout<<"\n---------------------------------------------------------------------------"<<endl;
cout<<"\t\t\t KNAPSACK PROBLEM "<<endl;
cout<<"\t\t\tMETODE GREEDY BY DENSITY "<<endl;
cout<<"\n---------------------------------------------------------------------------"<<endl;
cout<<"\nKapasitas : ";
cin>>m;
cout<<"Banyak item : ";
cin>>n;
for(i=0;i<n;i++)
{
p_no[i]=i+1;
cout<<"\nBarang "<<(i+1);
cout<<"\nBerat : ";
cin>>w[i];
cout<<"Profit : ";
cin>>p[i];
d[i]=(float)p[i]/w[i];
}
display();
for(i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(d[i]<d[j])
{
sort(p_no,i,j);
sort(w,i,j);
sort(p,i,j);
sort(d,i,j);
}
}
}
//display();
knapsack();
cout<<"\n\n";
system("PAUSE");
return EXIT_SUCCESS;
}
dan berikut outputnya :
ConversionConversion EmoticonEmoticon