最小机器重量 分支限界

#include <stdio.h>
#include <stdlib.h>
int bottom,Flag2;
int COST,n,m,*bestx;
int cc,cw,w[100][100];
int cp,c[100][100];
int bestw=1000;
int Flag;
int E;
int bext[100];
int bestxulie[100],sum;
//using namespace std;
struct Heapnode
{
int profit;
int weight;
int
level;
int prt;
int current;
};
struct Heapnode H[100];
struct Heapnode N;
void DeleteMin()
{
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++;
}
void Insert()
{
H[Flag].level=N.level;
H[Flag].profit=N.profit;
H[Flag].prt=N.prt;
H[Flag].current=N.current;
H[Flag].weight=N.weight;
Flag++;
}
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();
}
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+w[i][j];
ct=cp+c[i][j];
if(ct<=COST&&i<=n)
{
if(i==n)
{
int k;
if(wt<bestw)
{
bestw=wt;
for(k=1; k<n-1; k++)
bestxulie[k]=bext[k+2];
bestxulie[n]=j;
for(k=1; k<n-1; k++)
sum+=w[k][bestxulie[k]];
sum+=w[n][j];
for(k=1; k<=n; k++)
{
if(w[n-1][k]==(bestw-sum))
bestxulie[n-1]=k;
}
}
}
else
AddLiveNode(ct,wt,i+1,j);
}
}
if(bottom==Flag)
break;
DeleteMin();
cw=N.weight;
cp=N.profit;
i=N.level;
Flag2=N.current;
bext[i]=N.prt;
}
return bestw;
}
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",&c[i][j]);
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
scanf("%d",&w[i][j]);
printf("最小重量为：n");
printf("%dn",MinWeightMachine());
printf("每个物品对应的供应商为:n");
for(i=1; i<=n; i++)
printf("%d
",bestxulie[i]);
return 0;
}