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