蛮力法求解背包问题.doc

《蛮力法求解背包问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、/*程序说明：此程序用来解决蛮力法求解背包问题,运行程序输入背包容量和物品数量，屏幕打印运算过程，最后运算时间输出到文件*/先看下运行图片#include/#include#include#include#include#defineMAXSIZE20000//#defineBAGWEIGHT200inta[MAXSIZE]={0};intarray[MAXSIZE]={0};intweightarray[MAXSIZE]={0};/*存放各物品重量*

2、/intvaluearray[MAXSIZE]={0};/*存放各物品价值*/intlastweight[MAXSIZE]={0};intlastvalue[MAXSIZE]={0};intqq=0;/*上面的数组，变量都是蛮力法所用到，下面的都是分支限界法所用到*/intBAGWEIGHT;/*背包的载重*/intn;/*物品的数量*/intweightarrayb[MAXSIZE]={0};intvaluearrayb[MAXSIZE]={0};floatcostarrayb[MAXSIZE]={0};intfinalb[MAXSIZE]={0

3、};intfinalweightb[MAXSIZE]={0};/*蛮力法输出穷举的每一种可能，并求出下界*/voidprint(){inti,xx,cc,weight,value,pp,aa;weight=0;value=0;cc=1;xx=1;aa=1;for(i=1;i<=n;i++){if(a[i]){printf("%3d",i);array[xx]=i;xx++;/*array[]={1,2,3,4}*/}}inttempi=0;while(xx

4、c]!=0){weight=weight+weightarray[array[cc]];cc++;}while(array[aa]!=0){value=value+valuearray[array[aa]];aa++;}printf("%-20d",weight);char*str;str="overflow";if(weight>BAGWEIGHT){printf("%-20s",str);}else{printf("%-20d",value);lastweight[qq]=weight;lastvalue[qq]=value;qq++;}pri

5、ntf("");for(pp=1;pp<=xx;pp++){array[pp]=0;}}/*检验a[]数组，1的个数*/intjianyan(){inti,s=0;for(i=1;i<=n;i++){if(a[i]){s++;}}returns;}/*蛮力法*/voidfun(intt,intk){inti;if(t>n

6、

7、jianyan()>=k){return;}a[t]=1;if(jianyan()==k){print();}else{fun(t+1,k);}a[t]=0;fun(t+1,k);}/*从文件读取数据*/voidread()

8、{intnn=1,ii=1;inti=1;FILE*fp;fp=fopen("in.dat","rb");while(!feof(fp)){if(fscanf(fp,"%d%d",&weightarray[nn],&valuearray[nn])!=EOF){nn++;i++;}else{break;}}fclose(fp);printf("weight");printf("value");for(ii=1;ii

9、;printf("");}}/*自动生成文件*/voidbecome(){inti;FILE*fp;fp=fopen("in.dat","w");//srand(unsigned(time(NULL)));for(i=0;i

10、rintf("请输入物品数量（大于0的整数）：");scanf("%d",&n);floattime_usea=0;flo