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

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

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

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

3、位置,此时在它之前(后)的记录均不大于它.{intshuzhou;//定义枢轴L.r[0]=L.r[low];//用第一个记录作为枢轴记录shuzhou=L.r[low].q;while(low=shuzhou)--high;L.r[low]=L.r[high];while(low

4、t(Bags&L,intlow,inthigh)//快速排序//对顺序表L[low....high]作快速排序{intshuzhou;if(low

5、值递减顺序装入物品while(i<=n&&L.r[i].w<=left){left-=L.r[i].w;bound+=L.r[i].v;i++;}//装满背包if(i<=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

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

7、100个!）："<>n;if(n>100){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<

8、执行0-1背包问题主算法knapsack(c);//输出结果for(i=1;i<=n;i++)