分支限界法解决最小重量机器问题.doc

《分支限界法解决最小重量机器问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#include#includeintbottom,Flag2;intCOST,n,m,*bestx;intcc,cw,w[100][100];intcp,c[100][100];intbestw=1000;intFlag;intE;intbext[100];intbestxulie[100],sum;structHeapnode{intprofit;intweight;intlevel;intprt;intcurrent;};structHeapnodeH[100];structHeapnodeN;intM

2、inWeightMachine(){inti=1,j,wt=0,ct=0;cw=0;cp=0;intbesTypep=0;while(1){for(j=1;j<=m;j++){wt=cw+w[i][j];ct=cp+c[i][j];if(ct<=COST&&i<=n){if(i==n){intk;if(wt

3、n][j];for(k=1;k<=n;k++){if(w[n-1][k]==(bestw-sum))bestxulie[n-1]=k;}}}elseAddLiveNode(ct,wt,i+1,j);}}if(bottom==Flag)break;DeleteMin(N);cw=N.weight;cp=N.profit;i=N.level;Flag2=N.current;bext[i]=N.prt;}returnbestw;}voidAddLiveNode(intcp,intcw,inti,intj){N.profit=cp;N.weight=cw

4、;N.level=i;N.current=j;N.prt=Flag2;Insert(N);}voidDeleteMin(){N.level=H[bottom].level;N.profit=H[bottom].profit;N.prt=H[bottom].prt;N.current=H[bottom].current;N.weight=H[bottom].weight;bottom++;}voidInsert(){H[Flag].level=N.level;H[Flag].profit=N.profit;H[Flag].prt=N.prt;H[F

5、lag].current=N.current;H[Flag].weight=N.weight;Flag++;}intmain(){inti,j;scanf("%d%d%d",&n,&m,&COST);for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&c[i][j]);for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&w[i][j]);printf("最小重量为：");printf("%d",MinWeightMachine());printf("每个物品对

6、应的供应商为:");for(i=1;i<=n;i++)printf("%d",bestxulie[i]);return0;}