贪心算法 背包问题代码 c语言 用贪心算法求解普通背包问题的C++代码

用贪心算法求解普通背包问题的C++代码

3月6日 125次阅读 来源: 贪心算法

#include

#define M 100

void display(int &n,double &C,double s[M],double p[M])

{

int i;

cout<

cin>>n;

cout<

cout<

cin>>C;

cout<

cout<

s[0]=0;

for(i=1;i<=n;i++)

cin>>s[i];

cout<

p[0]=0;

for(i=1;i<=n;i++)

cin>>p[i];

};

void asc(int n,double s[M],double p[M])//按照价值密度的降序排列；

{

int i,j;

double temp1,temp2,temp3,c[M];

for(i=1;i<=n;i++)

c[i]=p[i]/s[i];

for(i=1;i

for(j=1;j<=n-i;j++)

if(c[j]

{

temp1=p[j];p[j]=p[j+1];p[j+1]=temp1;

temp2=s[j];s[j]=s[j+1];s[j+1]=temp2;

temp3=c[j];c[j]=c[j+1];c[j+1]=temp3;

}

};

void knapsack(int n,double C,double s[M],double p[M],double x[M])//,double totalp)

{

int i;

double c1;

asc(n,s,p);

c1=C;

while(c1!=0)

{

for(i=1;i<=n;i++)

{

if(s[i]<=c1)

{

x[i]=1;

c1=c1-s[i];

}

else if(s[i]>c1)

{

x[i]=c1/s[i];

c1=0;

}

//totalp=totalp+p[i]*x[i];

}

}

};

void main()

{

int i,n;

double C=0,totalp=0,s[M],p[M],x[M];

char ch;

while(1)

{

display(n,C,s,p);

knapsack(n,C,s,p,x);//,totalp);

cout<

for(i=1;i<=n;i++)

cout<

cout<

// for(i=1;i<=n;i++)

//cout<

// cout<

cout<

for(i=1;i<=n;i++)

{

cout<

totalp=totalp+p[i]*x[i];

}

cout<

cout<

cout<

cin>>ch;

if(ch==’Y’||ch==’y’)

continue;

else

break;

}

}