C#使用回溯法解决背包问题实例分析
本文实例讲述了C#使用回溯法解决背包问题的方法。分享给大家供大家参考。具体如下:
背包问题描述:
给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高
实现代码:
usingSystem; usingSystem.Collections.Generic; usingSystem.Text; namespaceBackRack { //要装入书包的货物节点 classBagNode { publicintmark;//货物编号,从0开始记 publicintweight;//货物重量 publicintvalue;//货物价值 publicBagNode(intm,intw,intv) { mark=m; weight=w; value=v; } } //根据货物的数目,建立相应的满二叉树,如:3个货物,需要建立15个节点的二叉树,共三层(根节点所在的层记为0) classBulidFullSubTree { publicstaticinttreeNodeNum=0;//满二叉树节点总数 publicintnoleafNode=0;//满二叉树出去叶子节点外所剩余的非叶子节点 publicstaticTreeNode[]treeNode;//存储满二叉树所有节点的数组 publicBulidFullSubTree(intnodeNum) { treeNodeNum=Convert.ToInt32(Math.Pow(2,nodeNum+1)-1); noleafNode=Convert.ToInt32(treeNodeNum-Math.Pow(2,nodeNum)); treeNode=newTreeNode[treeNodeNum]; for(inti=0;i<treeNodeNum;i++) { treeNode[i]=newTreeNode(i.ToString()); //对二叉树的所有节点初始化 } for(inti=0;i<noleafNode;i++) { //建立节点之间的关系 treeNode[i].left=treeNode[2*i+1]; treeNode[i].right=treeNode[2*i+2]; treeNode[2*i+1].bLeftNode=true; //如果是左孩子,则记其标识变量为true treeNode[2*i+2].bLeftNode=false; } treeNode[0].level=0;//约定根节点的层数为0 //根据数组下标确定节点的层数 for(inti=1;i<=2;i++) { treeNode[i].level=1; } for(inti=3;i<=6;i++) { treeNode[i].level=2; } for(inti=7;i<=14;i++) { treeNode[i].level=3; } } } //利用回溯法寻找最优解的类 classDealBagProblem { publicTreeNode[]treeNode=BulidFullSubTree.treeNode; //获取建立好的二叉树 intmaxWeiht=0;//背包最大承重量 inttreeLevel=Convert.ToInt32(Math.Floor(Math.Log(BulidFullSubTree.treeNodeNum,2)))+1; //二叉树的最大层数 int[]optionW=newint[100];//存储最优解的数组 int[]optionV=newint[100];//存储最优解的数组 inti=0;//计数器,记录相应数组的下标 intmidTw=0;//中间变量,存储程序回溯过程中的中间值 intmidTv=0;//中间变量,存储程序回溯过程中的中间值 intmidTw1=0;//中间变量,存储程序回溯过程中的中间值 intmidTv2=0;//中间变量,存储程序回溯过程中的中间值 BagNode[]bagNode;//存储货物节点 string[]solution=newstring[3]; //程序最终所得的最优解,分别存储:最优价值,总重量,路径 //int[]bestWay=newint[100]; TraceNode[]Optiontrace=newTraceNode[100];//存储路径路径 publicDealBagProblem(BagNode[]bagN,TreeNode[]treeNode,intmaxW) { bagNode=bagN; maxWeiht=maxW; for(inti=0;i<Optiontrace.Length;i++) { //将路径数组对象初始化 Optiontrace[i]=newTraceNode(); } } //核心算法,进行回溯 //cursor:二叉树下一个节点的指针;tw:当前背包的重量;tv:当前背包的总价值 publicvoidBackTrace(TreeNodecursor,inttw,inttv) { if(cursor!=null)//如果当前节点部位空值 { midTv=tv; midTw=tw; if(cursor.left!=null&&cursor.right!=null) //如果当前节点不是叶子节点 { //如果当前节点是根节点,分别处理其左右子树 if(cursor.level==0) { BackTrace(cursor.left,tw,tv); BackTrace(cursor.right,tw,tv); } //如果当前节点不是根节点 if(cursor.level>0) { //如果当前节点是左孩子 if(cursor.bLeftNode) { //如果将当前货物放进书包而不会超过背包的承重量 if(tw+bagNode[cursor.level-1].weight<=maxWeiht) { //记录当前节点放进书包 Optiontrace[i].mark=i; Optiontrace[i].traceStr+="1"; tw=tw+bagNode[cursor.level-1].weight; tv=tv+bagNode[cursor.level-1].value; if(cursor.left!=null) { //如果当前节点有左孩子,递归 BackTrace(cursor.left,tw,tv); } if(cursor.right!=null) { //如果当前节点有左、右孩子,递归 BackTrace(cursor.right,midTw,midTv); } } } //如果当前节点是其父节点的右孩子 else { //记录当前节点下的tw,tv当递归回到该节点时,以所记录的值开始向当前节点的右子树递归 midTv2=midTv; midTw1=midTw; Optiontrace[i].traceStr+="0"; if(cursor.left!=null) { BackTrace(cursor.left,midTw,midTv); } if(cursor.right!=null) { //递归所传递的midTw1与midTv2是先前记录下来的 BackTrace(cursor.right,midTw1,midTv2); } } } } //如果是叶子节点,则表明已经产生了一个临时解 if(cursor.left==null&&cursor.right==null) { //如果叶子节点是其父节点的左孩子 if(cursor.bLeftNode) { if(tw+bagNode[cursor.level-1].weight<=maxWeiht) { Optiontrace[i].traceStr+="1"; tw=tw+bagNode[cursor.level-1].weight; tv=tv+bagNode[cursor.level-1].value; if(cursor.left!=null) { BackTrace(cursor.left,tw,tv); } if(cursor.right!=null) { BackTrace(cursor.right,midTw,midTv); } } } //存储临时优解 optionV[i]=tv; optionW[i]=tw; i++; tv=0; tw=0; } } } //从所得到的临时解数组中找到最优解 publicstring[]FindBestSolution() { intbestValue=-1;//最大价值 intbestWeight=-1;//与最大价值对应的重量 intbestMark=-1;//最优解所对应得数组编号(由i确定) for(inti=0;i<optionV.Length;i++) { if(optionV[i]>bestValue) { bestValue=optionV[i]; bestMark=i; } } bestWeight=optionW[bestMark];//重量应该与最优解的数组下标对应 for(inti=0;i<Optiontrace.Length;i++) { if(Optiontrace[i].traceStr.Length==bagNode.Length&&i==bestMark) { //找到与最大价值对应得路径 solution[2]=Optiontrace[i].traceStr; } } solution[0]=bestWeight.ToString(); solution[1]=bestValue.ToString(); returnsolution; } } classProgram { staticvoidMain(string[]args) { //测试数据(货物) //Node[]bagNode=newNode[100]; //BagNodebagNode1=newBagNode(0,5,4); //BagNodebagNode2=newBagNode(1,3,4); //BagNodebagNode3=newBagNode(2,2,3); //测试数据(货物) BagNodebagNode1=newBagNode(0,16,45); BagNodebagNode2=newBagNode(1,15,25); BagNodebagNode3=newBagNode(2,15,25); BagNode[]bagNodeArr=newBagNode[]{bagNode1,bagNode2,bagNode3}; BulidFullSubTreebfs=newBulidFullSubTree(3); //第3个参数为背包的承重 DealBagProblemdbp=newDealBagProblem(bagNodeArr,BulidFullSubTree.treeNode,30); //找到最优解并将其格式化输出 dbp.BackTrace(BulidFullSubTree.treeNode[0],0,0); string[]reslut=dbp.FindBestSolution(); if(reslut[2]!=null) { Console.WriteLine("该背包最优情况下的货物的重量为:{0}\n货物的最大总价值为:{1}",reslut[0].ToString(),reslut[1].ToString()); Console.WriteLine("\n"); Console.WriteLine("该最优解的货物选择方式为:{0}",reslut[2].ToString()); char[]r=reslut[2].ToString().ToCharArray(); Console.WriteLine("被选择的货物有:"); for(inti=0;i<bagNodeArr.Length;i++) { if(r[i].ToString()=="1") { Console.WriteLine("货物编号:{0},货物重量:{1},货物价值:{2}",bagNodeArr[i].mark,bagNodeArr[i].weight,bagNodeArr[i].value); } } } else { Console.WriteLine("程序没有找到最优解,请检查你输入的数据是否合适!"); } } } //存储选择回溯路径的节点 publicclassTraceNode { publicintmark;//路径编号 publicstringtraceStr;//所走过的路径(1代表取,2代表舍) publicTraceNode(intm,stringt) { mark=m; traceStr=t; } publicTraceNode() { mark=-1; traceStr=""; } } //回溯所要依附的满二叉树 classTreeNode { publicTreeNodeleft;//左孩子指针 publicTreeNoderight;//右孩子指针 publicintlevel;//数的层,层数代表货物的标识 stringsymb;//节点的标识,用其所在数组中的下标,如:“1”,“2” publicboolbLeftNode;//当前节点是否是父节点的左孩子 publicTreeNode(TreeNodel,TreeNoder,intlev,stringsb,boolln) { left=l; right=r; level=lev; symb=sb; bLeftNode=ln; } publicTreeNode(stringsb) { symb=sb; } } }
希望本文所述对大家的C#程序设计有所帮助。