分支限界法求解背包问题/*此程序实现，分支限界法求解背包问题，分支限界法是根据上界=当前背包的价值+背包剩余载重* （剩余物品最大价值/质量）*/分支r 10 I 分S： 104 1.200060' 6 2.i/eeoe#i nclude <stdio.h> #i nclude <stdlib.h>#include <time.h>#include <sys/time.h>#include <assert.h>#define MAXSIZE 20000//#define BAGWEIGHT 200 int a[MAXSIZE] = {0};int array[MAXSIZE] = {0};int weightarray[MAXSIZE] = {0}; /* 存放各物品重量*/int valuearray[MAXSIZE] = {0}; /* 存放各物品价值*/int lastweight[MAXSIZE]={0}; int lastvalue[MAXSIZE]={0}; int qq=0;/* 上面的数组，变量都是蛮力法所用到，下面的都是分支限界法所用到*/ int BAGWEIGHT; /* 背包的载重*/int n; /* 物品的数量*/int weightarrayb[MAXSIZE] = {0}; intvaluearrayb[MAXSIZE] = {0}; float costarrayb[MAXSIZE] = {0}; intfinalb[MAXSIZE] = {0};int finalweightb[MAXSIZE] = {0};/* 从文件读取数据*/void readb()int nn = 1,ii = 1;int i = 1;FILE *fp;fp = fopen("in.dat","rb");while(!feof(fp)){if(fscanf(fp,"%d%d",&weightarrayb[nn],&valuearrayb[nn]) != EOF)nn++;i++;elsebreak;fclose(fp);printf(" weight ");printf("value\n");for(ii = 1;ii < nn;ii++)printf("no%d: %-5d%-5d",ii,weightarrayb[ii],valuearrayb[ii]);printf("\n");/* 把读取的数据按照性价比从大到小排序*/ void rangeb()int i,j,k;int tempvalue,tempweight,tempcost;for(i = 1;i <= n;i++)printf(" weight ");costarrayb[i] = valuearrayb[i]/weightarrayb[i];for(j = 1;j <= n;j++)for(k = j;k <= n;k++)if(costarrayb[j] < costarrayb[k+1])tempcost = costarrayb[j];costarrayb[j] = costarrayb[k+1];costarrayb[k+1] = tempcost;tempweight = weightarrayb[j];weightarrayb[j] = weightarrayb[k+1];weightarrayb[k+1] = tempweight;tempvalue = valuearrayb[j];valuearrayb[j] = valuearrayb[k+1];valuearrayb[k+1] = tempvalue;printf("value ");printf("cost\n");for(i = 1;i <= n;i++)printf("no%d: %-5d%-5d %- f",i,weightarrayb[i],valuearrayb[i],costarrayb[i]); printf("\n");/* 分支限界法运算*/void branchb()int i,k,j,u = 1;int emptyweight = BAGWEIGHT;int tempweight = 0;int tempvalue = 0;float ub;float exub;int extempweightb[MAXSIZE] = {0};int extempvalueb[MAXSIZE] = {0};int exemptyweightb[MAXSIZE] = {0};int allweight = 0;int allvalue = 0;ub = tempvalue + emptyweight * costarrayb[1];exemptyweightb[0] = BAGWEIGHT;printf("include 0: weight=0 value=0 ub = %f\n",ub);printf("\n");i = 1;while(weightarrayb[i] != 0)tempweight = tempweight + weightarrayb[i];tempvalue = tempvalue + valuearrayb[i];emptyweight = BAGWEIGHT - tempweight;if(tempweight > BAGWEIGHT)printf("include %d: weight=%d can't\n",i,tempweight);tempweight = extempweightb[i-1];tempvalue = extempvalueb[i-1];emptyweight = exemptyweightb[i-1];ub = 0;elseub = tempvalue + emptyweight * costarrayb[i+1];printf("include %d: weight=%d value=%d ub=%f\n",i,tempweight,tempvalue,ub); extempvalueb[i] = tempvalue;extempweightb[i] = tempweight;exemptyweightb[i] = emptyweight;exub = extempvalueb[i-1] + exemptyweightb[i-1] * costarrayb[i+1]; printf("exclude %d: weight=%d value=%dub=%f\n",i,extempweightb[i-1],extempvalueb[i-1],exub);printf("\n");if(ub < exub || ub == 0)finalb[i] = 2;if(ub >= exub)finalb[i] = 1;i++;printf("the final answer is: ");for(i = 1;i <= n;i++)if(finalb[i] == 1)printf("%d ",i);finalweightb[u] = i;u++;else if(finalb[i] == 2)continue;printf("\n");for(i = 1;i <= u;i++)allweight = allweight + weightarrayb[finalweightb[i]]; allvalue = allvalue + valuearrayb[finalweightb[i]];printf("the final weight is :%d\n",allweight);printf("the final value is : %d\n",allvalue);/* 自动生成文件*/void become()int i;FILE *fp;fp = fopen("in.dat","w");//srand(unsigned(time(NULL)));for(i=0;i<n;i++)fprintf(fp,"%d %d\n",rand()%9+1,rand()%41+10);fclose(fp);/* 删除文件*/void del()remove("in.dat");int main()printf(" 请输入背包负重(大于0 的整数):"); scanf("%d",&BAGWEIGHT);printf(" 请输入物品数量(大于0 的整数):"); scanf("%d",&n);float time_usea=0;float time_useb=0;struct timeval starta;struct timeval enda;struct timeval startb;struct timeval endb;int k = 0,i,j,u,loop;loop=0;gettimeofday(&startb,NULL);become();readb();由于分支限界太效率，时常显示 0 毫秒，为了能读出时间，让其运行 100 次后总时间再除以 100*/rangeb();branchb();gettimeofday(&endb,NULL);time_useb=(__sec)*1000+(_usec- _usec)/1000;// 毫秒printf("\n");for(i=0;i<100;i++) /*printf("It took you %f 毫秒\n", time_useb/100);/* 最后把算到的时间读出到文件*/FILE *fp = NULL;fp = fopen("OUT.DAT", "a+");if(NULL == fp)printf("wrong");return 0;//fprintf(fp, " 蛮力: %d %d %f\n", BAGWEIGHT,n,time_usea); fprintf(fp, " 分支: %d %d %f\n", BAGWEIGHT,n,time_useb/100); fclose(fp);del(); /* 要运算多次，生成多次文件，所以每次算完删除文件*/printf（" 如果需要再算一次，请按1\n"）; printf（" 如果需要退出，请按2\n"）; scanf("%d",&loop);switch(loop)case 1:return main();case 2:return;default:return;return 0;}。