背包问题《贪心算法》

给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? （说明，以下算法与教材147页给出的算法思想是一样的，教材上的算法事先对物品信息进行了排序）

void Knapsack(int n,float M,float v[],float w[],float x[])

{

       Sort(n,v,w);

       int i;

       for (i=1;i<=n;i++) x[i]=0;

       float c=M;

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

          if (w[i]>c) break;

          x[i]=1;

          c-=w[i];

          }

       if (i<=n) x[i]=c/w[i];//最后一个物品选择部分装入

}

 

#include<iostream>

using namespace std;

#define N 100

void main(){

float p[N];

float w[N];

float x[N];

float c,cw,s,h;

int i,j,n;

 

cout<<"input n:"<<endl;

cin>>n;

cout<<"input c:"<<endl;

cin>>c;

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

{

cout<<"input w"<<i<<","<<"p"<<i<<":   ";

cin>>w[i];

cin>>p[i];

}

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

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

{

if(p[i]/w[i]<p[j]/w[j]){

h=p[i];p[i]=p[j];p[j]=h;

h=w[i];w[i]=w[j];w[j]=h;

}

}

 cw=c;s=0;//cw为背包可装的重量

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

 if(w[i]>cw) break;

 else {

 x[i]=1.0;

 cw=cw-w[i];

 s=s+p[i];

 }

 }

x[i]=(float)(cw/w[i]);

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

cout<<"装包:";

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

if(x[i]<1) break;

else cout<<"装入重量为"<<w[i]<<"效益为"<<p[i]<<"的物品"<<endl;

if(x[i]>0&&x[i]<1)

cout<<"装入重量为"<<w[i]<<"效益为"<<p[i]<<"的物品"<<"百分之"<<x[i]*100<<endl;

 

cout<<"最大效益为"<<s<<endl;

}