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

1、分支限界法解决最小重量机器问题#include #include int bottom,Flag2;int COST,n,m,*bestx;int cc,cw,w100100;int cp,c100100;int bestw=1000;int Flag;int E;int bext100;int bestxulie100,sum;struct Heapnodeint profit;int weight;int level;int prt;int current;struct Heapnode H100;struct Heapnode N;int MinWeightMachine()int i=

2、1,j,wt=0,ct=0;cw=0;cp=0;int besTypep=0;while(1)for(j=1; j=m; j+)wt=cw+wij; ct=cp+cij; if(ct=COST&i=n) if(i=n)分支限界法解决最小重量机器问题int k; if(wtbestw) bestw=wt; for(k=1; kn-1; k+) bestxuliek=bextk+2; bestxulien=j; for(k=1; kn-1; k+) sum+=wkbestxuliek; sum+=wnj; for(k=1; k=n; k+) if(wn-1k=(bestw-sum) bestxul

3、ien-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; bexti=N.prt;return bestw;void AddLiveNode(int cp,int cw,int i,int j)N.profit=cp;N.weight=cw;N.level=i; N.current=j;N.prt=Flag2; Insert(N);void DeleteMin()分支限界法解决最小重量机器问题N.l

4、evel=Hbottom.level;N.profit=Hfit;N.prt=Hbottom.prt;N.current=Hbottom.current;N.weight=Hbottom.weight; bottom+;void Insert()HFlag.level=N.level;HFfit=N.profit;HFlag.prt=N.prt;HFlag.current=N.current;HFlag.weight=N.weight;Flag+;int main()int i,j; scanf(%d%d%d,&n,&m,&COST); for(i=1; i=n; i+)for(j=1; j=m; j+)scanf(%d,&cij);for(i=1; i=n; i+)for(j=1; j=m; j+) scanf(%d,&wij); printf( 最小重量为： n); printf(%dn,MinWeightMachine(); printf( 每