算法分析回溯法实现0-1背包(c++)

《算法分析回溯法实现0-1背包(c++)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、本程序实现0-1背包问题算法(回溯法)/**本程序实现0-1背包问题算法(回溯法)**/#includeusingnamespacestd;#defineMAXSIZE100#defineTRUE1#defineFALSE0#defineERROR-1typedeffloatvalue;typedeffloatweight;typedefintKeyType;//定义关键字类型为整数类型typedefstruct//元素定义{weightw;//重量valuev;//价值valueq;//单位重量价值intindex;//序号booljob;//表示是否被用}Bag;typ

2、edefstruct//定义背包集{Bagr[MAXSIZE+1];//r[0]闲置或用作“哨兵单元”intlength;//背包个数}Bags;intn;//包个数inti;//辅助整型变量weightc;//背包的容量weightcw;//当前重量valuebestp=0;//当前最优价值valuecp;//当前价值BagsL;//定义背包集intPartition(Bags&L,intlow,inthigh)//快速排序//交换顺序表L中子表r[low.....high]的记录,枢轴记录到位,并返回其所在位置,此时在它之前(后)的记录均不大于它.{intshuzhou;//定义枢轴L.r

3、[0]=L.r[low];//用第一个记录作为枢轴记录shuzhou=L.r[low].q;while(low=shuzhou)--high;L.r[low]=L.r[high];while(low

4、hou;if(low

5、=n)bound+=L.r[i].v*left/L.r[i].w;returnbound;}//boundvoidbacktrack(inti){if(i>n){//到达叶子结点bestp=cp;return;}//搜索子树if(cw+L.r[i].w<=c){//进入左子树cw+=L.r[i].w;cp+=L.r[i].v;//L.r[i].job=true;//选中backtrack(i+1);cw-=L.r[i].w;cp-=L.r[i].v;//L.r[i].job=false;//未选中}if(bound(i+1)>bestp)//进入右子树backtrack(i+1);}//bac

6、ktrackvoidknapsack(weightc)//0-1背包问题主算法{QuickSort(L,1,L.length);backtrack(1);//回溯搜索}//knapsackintmain(){//输入要选择的背包信息cout<<"请输入背包的容量:"<>c;cout<<"请输入背包个数（注意：最大作业数不能超过100个!）："<>n;if(n>100){cout<<"你输入的背包个数太大!!!"<

7、){cout<<"请输入第个"<>L.r[i].w;cout<<"请输入第个"<>L.r[i].v;L.r[i].q=L.r[i].v/L.r[i].w;//单位重量价值L.r[i].index=i;//索引号cout<