运用贪心策略解决0 1背包问题
void beibao(int *w,int *v,int *x,int n,int *C)
{
int i,j,temp;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(v[i]/w[i]<v[j]/w[j])
{
temp=v[i];
v[i]=v[j];
v[j]=temp;
temp=w[i];
w[i]=w[j];
w[j]=temp;
}
for(i=0;i<n;i++)
x[i]=0;
for(i=0;w[i]<=*C;i++)
{
x[i]=1;
*C=*C-w[i];
}
}
void main()
{
int i,*w,*v,*x,n,C;
cout<<"请输入物品数"<<endl;
cin>>n;
w=new int(n);//动态分配内存
v=new int(n);
x=new int(n);
cout<<"请输入背包的容量"<<endl;
cin>>C;
cout<<"请分别输入"<<n<<"个物品的重量:"<<endl;
for(i=0;i<n;i++)
cin>>w[i];
cout<<"请分别输入"<<n<<"个物品的价值:"<<endl;
for(i=0;i<n;i++)
cin>>v[i];
beibao(w,v,x,n,&C);
cout<<"应用贪心策略装入背包的物品的重量分别为:"<<endl;
for(i=0;i<n-1;i++)
if(x[i]==1)
cout<<" "<<w[i];
cout<<" "<<C<<"/"<<w[i]<<endl;
}