最小重量机器(分支限界法).doc

精品文档附件二：附件一：#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 Heapnode int profit; int weight; int level; int prt; int current;struct Heapnode H100;struct Heapnode N;int MinWeightMachine() int i=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) bestxulien-1=k; else AddLiveNode(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.level=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(每个物品对应的供应商为:n); for(i=1; i=n; i+) printf(%d ,bestxu