资源描述：
《算法基础实践-01背包问题.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、算法基础实践-0-1背包问题组名：阿迪王包包里有糖组长：杨祺鹏组员:刘锦权'张鑫，胥樊，辜克生(191071班)’崔海涛(191071)指导老师：彭磊班号：191072,191071%1.0J背包问题介绍在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1,W-2……Wn,与之相对应的价值为P1,P2……Pno求出获得最大价值的方案。注意：在木题屮，所有的体积值均为整数，也就是说，每件物品只有取或者不取两种可能，不可以分解物品.%1.背包问题的实质背包问题是一种组合优化的NP完全问题，相似的问题同样也是出现在商业,组合数学等行业，因此以最快速度和最精确得解决背色
2、问题是非常有前景的.%1.本小组的研究冃标针对0/背包这种特殊的背包问题，我们主要研究解决这个问题的传统算法以及最近新兴的算法，并且找出各种算法的优劣性，给出在不同情况应该用哪种算法才能最快最精确得解决0/背包问题.%1.实践过程传统算法选取:回溯法，遗传算法新型算法选取:蚁群算法，模拟退火算法，对这个四个算法，我们用一个形象的比喻先来介绍一下。问题：为了寻找世界上最高的山，一群兔子开始想办法（为了寻找最优路径）。一些兔子总是向着比口己高的山峰跑去。…局部搜索算法，回溯法一些兔子喝醉了，他们跑了很久很久，在这一段吋间内，他们有可能进入平地，也可能进入高峰。然后兔子们醒酒了
3、，他们向着最高的山峰跑去。…模拟退火算法一些兔子失忆了，被发射到了太空，并且在太空屮随机得被发射到地球上,他们不知道口己的使命是什么。但是，如果你过儿年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到最高的山峰。…遗传算法一些兔子在找到一个高山的吋候，在山上拉了一坨便便使得别的兔子能找到这座高山，并且吸引别的兔子过來，被找到的高山越來越多，最后会找到最高的山峰。…蚁群算法1.回溯法冋溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退冋一步重新选择，这种走不通就退冋再走的技术为回溯法.回溯法解决0/背包问题的优缺
4、点:因为冋溯法在构建解空间的时候要构建一棵完柴的二叉树（最传统冋溯法，没有进行优化）,因此时间复杂度是指数型的.当背包物品很少,经过测试为小于等于15的时候，冋溯法的效率是很高的,而且在1-15这一段数域内，解决时间相差无儿，因此，在背包物品较少的时候，使用I叫溯法是很不错的选择•但是,随着背包物品的增加，在解决18个物品的时候，计算时问超过了500MS.19个物品就经常计算不出,20个物品的时候，就己经溢出了int32这个值表示的范fflTo这是因为在构建解空间树的时候，就构建不出来了。冋溯法求解的流程图：流程图屮省略了开始构建解空间的部分，只写了回溯的算法。建立满二叉
5、树的程序和生成随机数据的程序略。冋溯算法的冋溯程序：classDealBagProblcm{publicTreeNode[]treeNode=Buiidl'ullSubTree.treeNode;//已经建好的二叉树intmaxWeiht=0;//背包最大承朿:戢inttreeLevel二Convert.Tolnt32(Math.Floor(Math.Log(BuiidlulISubTree.treeNodeNum,2)))+1；//二叉树的最大层数int[]optionW=newint[50000]:存储最优解的数组int[]optionV=newint[50000]存
6、储最优解的数组inti=0;//计数器,记录相应数组的下标intmidTw=0;//存储过程中的重量intmidTv=0;//存储过程中的价值intinidTwl=0;//同上intmidTv2=0://同上BagNode[]bagNode;存储货物节点string[]solution二newstring⑵；//程序最终所得的最优解,分别存储:最优价值，总重量publicDealBagProblem(BagNode[]bagN,TreeNode[]LreeNode,intmaxW)bagNode=bagN;inaxWeiht二maxW:}//cursor:二叉树下一个节点
7、的指针；tv：当前背包的重昴：tv：当前背包的总价值publicvoidBackTrace(TreeNodecursor,inttw,inttv){if(cursor!=null)，如呆当前肖点部位空值(midTv二tv;midTw二tw;if(cursor,left!=null&&cursor,right!=nul1)7如果当前if点不兄叶了节点//如果当前节点是根节点,分别处理其左右了树if(cursor・level二二0)BackTrace(cursor,left,tw,tv);//如果当前节点是左孩子if(curso
