贪婪法求解背包问题

贪婪法求解背包问题

算法设计与分析

第五章贪婪法的算法实现代码

1、算法1：贪婪法求解背包问题

#include<iostream>

using namespace std;

#define n 10

#define M 30

typedef struct

{

float p;//每个物体的价值

float w;//每个物体的重量

float v;//每个物体的价值重量比

}object;

void swap(object &x,object &y)

{

object t=x;

x=y;

y=t;

}

void bubble(object a[])

{

int i,j;

for(i=n-1;i>0;i--)

for(j=0;j<i;j++)

{

if(a[j].v<a[j+1].v)

swap(a[j],a[j+1]);

}

}

float f(object o[],float d,float x[])

{

int i,j;

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

{

o[i].v=o[i].p/o[i].w;

x[i]=0;

}

float m=M;

bubble(o);

for(int i=0;i<n;i++)

{

贪婪法求解背包问题

cout<<"物体的价值比重是："<<o[i].v<<"\t";

if((i+1)%2==0)

cout<<endl;

}

for(int j=0;j<n;j++)

{

if(o[j].w<=m)

{

d=d+o[j].p;

m=m-o[j].w;

x[j]=1;

}

else

{

x[j]=m/o[j].w;

d+=x[j]*o[j].p;

break;

}

}

return d;

}

void main()

{

object o[n];

float a[]={3,4,2,5,7,10,1,6,9,8};

float b[]={7,6,6,8,12,15,4,10,14,13};

for(int i=0;i<n;i++)

{

o[i].w=a[i];

o[i].p=b[i];

}

float d=0;

float x[n];

d=f(o,d,x);

cout<<"最优值为："<<d<<endl;

for(int i=0;i<n;i++)

cout<<"物体的比重为："<<"x["<<i<<"]="<<x[i]<<"\n";

system("pause");

}