《贪心算法求解背包问题C语言描述》由会员分享，可在线阅读，更多相关《贪心算法求解背包问题C语言描述（5页珍藏版）》请在金锄头文库上搜索。
1、贪心算法求解背包问题:#include#define maxnumber 20typedef struct nodefloat w;float v;int i;Object;float find(Object wp,int n,float M)float xmaxnumber;int i;float maxprice=0;for(i=l;i=n;i+)/初始化 xn;i=0;while(wpi.w M)xi=0.0;xwpi.i=l;M=M-wpi.w;i+；xwpi.i=M/wpi.w;输出解向量printff解向量是：n);for(i=l;i=n;i+)printf(,x%d=%f,i,x
2、i);printf(”n)；计算最大价值for(i=0;in;i+)maxprice=maxprice+wpi.v*xwpi.i;return maxprice;void main()Object wpmaxnumber;int ij,n;float C;背包的重量int flag;float maxprice,temp;printf(n请输入物品的种数:“)；scanf(”d”,&n);printf(请输入背包的重量:”)；scanf(”f”,&C);printf(Hn请输入物品的序号、重量和价值:for(i=0;in;i+)scanf(%d,&wpi.i);scanf(%f,&wpi.w)
3、;scanf(%f,&wpi.v);printf(n输入的物品是:n);输出物品“)；for(i=0;in;i+)printf(d”,wpii);printf(%f,wpi.w);printf(%f,wpi.v);printfCXn);用冒泡排序对物品按照单位价值进行降序排序for(i=l;i=i;j-)if(wpj-l.v/wpj-l.w wpj.v/wpj.w)temp=wpj-l.i;wpj-l.i=wpj.i;wpj.i=temp;temp=wpj-l.v;printf(n排序后的物品是：n);if(flag=O)break;wpj-l.v=wpj.v;wpj.v=temp;flag=l;输出物品for(i=0;in;i+)printf(%d,wpi.i);printf(”f”,wpi.w);printf(%f,wpi.v);printfCV*);maxprice=find(wp,n,C);printf(n 物品的重价值为:%f”,maxprice);)
