C语言背包问题求解全过程(贪心方法)

　　#include

　　using namespace std;

　　const int maxn = 1000;

　　float z[maxn];

　　void Sort(int n,float w[],float v[]){

　　for(int i=0;i

　　z[i]=v[i]/w[i];//用z[]存物品的单位重量价值

　　for(int i=0;i

　　for(int j=i+1;j

　　if(z[i]

　　float temp = z[i];

　　z[i] = z[j];

　　z[j]=temp;

　　float tempw = w[i];

　　w[i] = w[j];

　　w[j] = tempw;

　　float tempv = v[i];

　　v[i] = v[j];

　　v[j] = tempv;

　　}

　　}

　　}

　　}

　　void fire(int n,float w[],float v[],float x[],float pimax){

　　Sort(n,w,v);//根据单位重量物品的价值对物品进行排序

　　int i;

　　for(i=0;i

　　if(w[i]>pimax) break;

　　x[i] = 1; //x[]数组用来记录此次是否选择物品，1代表全部拿走，0代表不拿，小数代表部分拿

　　pimax -= w[i];

　　}

　　if(i<=n-1) x[i] = pimax/w[i];

　　}

　　int main(){

　　int n;

　　float pi=0;

　　float pimax,v[maxn],w[maxn],x[maxn];//w[],每个物品的重量,v[]代表每个物品的价值,pimax代表最大容量

　　memset(x,0,sizeof(x));

　　cout<<"请输入最大容量：";

　　cin>>pimax;

　　cout<<"请输入物品(物品可以任意分割)数量：";

　　cin>>n;

　　cout<<"请输入每个物品的重量和价值："<

　　for(int i=0;i

　　cin>>w[i]>>v[i];

　　}

　　fire(n,w,v,x,pimax);

　　for(int i=0;i

　　if(x[i]==1){

　　pi+=v[i];

　　}

　　else{

　　pi+=v[i]*x[i];

　　}

　　}

　　cout<<"最终收获的物品(物品可以任意分割)价值为："<

　　return 0;

　　}