《不可分割背包问题算法》由会员分享，可在线阅读，更多相关《不可分割背包问题算法（5页珍藏版）》请在金锄头文库上搜索。
1、#include stdio.h#include iostream.h typedef structfloat p;/物体的价值float w;/物体的重量OBJECT;OBJECT ZH100;/100 为最多 100 个物品OBJECT YQ100;/100 为最多 100 个物品OBJECT instance100;int inZH=0;int inYQ=0;float pZH=0.0;float wZH=0.0;物品放入背包的数量物品被遗弃的数量放入背包的物品总价值放入背包的物品总重量intn;/物品数量int key=1;下标，循环条件变量 float M;/ M物品重量 void
2、change_1();实现把价值重量比低的物品换出void change_2();/ZH.pVYQ.p 且减去 ZH.w 加 YQ.wV=M,实现交换增加价值void add_inZH();实现ZH中物品总重量还可再加的情况下从YQ中添加并把YQ中的物 品设为0void find_group();找出一组组合保存在ZHj void main() while(key)pZH=0;wZH=0;inZH=0;inYQ=0;/初始化变量for(int ji=0;jiv100;ji+)初始化变量ZHji.w=0;ZHji.p=0;YQji.w=0;YQji.p=0;printf(n欢迎使用背包问题算法！
3、 nn请输入物品数量：); scanf(%d, &n);printf(n请输入背包能装的物品总重量：);scanf(%f, &M);for(int pw=O; pwvn; pw+)手动赋值printf(n请输入第小个物品的价值，重量：n,pw+l); scanf(%f%f, &i nstancepw.p,&i nstancepw.w);find_group();找出一组组合保存在ZHjint inZH1=inZH;float pZH1=pZH,wZH1=wZH;change_1();实现把价值重量比低的物品换出add_inZH();/ZH中的物品价值重量比比YQ中低的且ZH.pVYQ.p且减去
4、 ZH.w加YQ.wV=M,实现交换增加价值change_2();实现ZH中物品总重量还可再加的情况下从YQ中添加并把YQ中 的物品设为0int inZH2=inZH;float pZH2=pZH,wZH2=wZH;while(1)if(inZH1!=inZH2llpZH1!=pZH2llwZH1!=wZH2)inZH1=inZH;pZH1=pZH;wZH1=wZH;change_1();add_inZH();change_2();inZH2=inZH;pZH2=pZH; wZH2=wZH;elsebreak;printf(n背包所装物品的价值和重量分别为：n);for(int i=0,j=0
5、;iinZH;i+)if(ZHi.w!=0)printf( 价值:3.0f 重量:3.0fn,1+j+,ZHi.p,ZHi.w); printf(”背包总价值最大为：%3.0f，背包总重量为：%3.0fn,pZH,wZH); printf(n 退出 0|继续 1n);scanf(%d, &key);void change_l()实现把价值重量比低的物品换出for(int i=O;ivinZH;i+)for(int j=O;jvinYQ;j+)if(ZHi.pv=YQj.p )&(ZHi.p/ZHi.w)v(YQj.p/YQj.w)&ZHi.p!=0) 实现把价值重量比低的物品换出放到YQ并把Y
6、Q中符合的放到ZH 中OBJECT temp;temp=ZHi;ZHi=YQj;YQj=temp;pZH=pZH-YQj.p+ZHi.p; wZH=wZH-YQj.w+ZHi.w;if(wZHM)重量超过了就从ZH减出来放到YQwhile(1)int ii=0;float zh=ZHii.p/ZHii.w;for(ii=1;iivi;ii+)把价值重量比最低的换出if(zh(ZHii.p/ZHii.w)zh=ZHii.p/ZHii.w;YQinYQ=ZHii;inYQ+;pZH-=ZHii.p;wZH-=ZHii.w;ZHii.p=0;ZHii.w=0;if(wZH=pZH )&(wZH-ZH
7、i.w+YQj.w)v=M )&ZHi.p!=O)/ZHpVYQ.p且减去ZH.w加YQ.wV=M,实现交换增加价值OBJECT temp;temp=ZHi;ZHi=YQj;/进行交换YQj=temp;pZH=pZH-YQj.p+ZHi.p; wZH=wZH-YQj.w+ZHi.w;void add_inZH()实现ZH中物品总重量还可再加的情况下从YQ中添加并把YQ中的物 品设为0if(wZHpt)找出价值大的pt=YQaddt.p;y=addt;if(YQaddt.p/YQaddt.w)pW)找出价值重量比最大的pW=YQaddt.p/YQaddt.w;y1=addt;if(wZH+YQy
8、.w)M)使用价值重量比最大的y=y1;if(wZHvM&YQy.w!=O)/把价值大的放到 ZH ZHi=YQy;添加到组合中 pZH=pZH+ZHi.p; wZH=wZH+ZHi.w;YQy.p=0;YQ y .w=0;addZH+;i+;if(wZHM)i-;YQy=ZHi;添加到遗弃中 pZH=pZH-ZHi.p;wZH=wZH-ZHi.w;ZHi.p=0;ZHi.w=0;addZH-;inZH+=addZH;/ZH中物品数量+addZHvoid find_group()找出一组组合保存在ZHjint j=0;wZH=instancej.w;物品总重量 pZH=instancej.p;物品总价值 ZHinZH=instancej;/物品添加进可能的组合 inZH+;for(j=l;jvn;j+)找出所以不同的组合if(wZHvM)少的就加进去ZHjwZH+=instancej.w;pZH+=instancej.p;ZHinZH=instancej;添加到组合中 inZH+;if(wZHM)超过了就减出来ZHinZH-1.w=0;ZHinZH-l.p=O;从组合中删除 YQinYQ=instancej;/物品添加进遗弃的组合 wZH-=instancej.w;pZH-=instancej.p;inZH-;inYQ+;
