C#使用回溯法解决背包问题实例分析
程序员文章站
2023-10-26 23:39:34
本文实例讲述了c#使用回溯法解决背包问题的方法。分享给大家供大家参考。具体如下:
背包问题描述:
给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何...
本文实例讲述了c#使用回溯法解决背包问题的方法。分享给大家供大家参考。具体如下:
背包问题描述:
给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高
实现代码:
using system; using system.collections.generic; using system.text; namespace backrack { //要装入书包的货物节点 class bagnode { public int mark;//货物编号,从0开始记 public int weight;//货物重量 public int value;//货物价值 public bagnode(int m, int w, int v) { mark = m; weight = w; value = v; } } //根据货物的数目,建立相应的满二叉树,如:3个货物,需要建立15个节点的二叉树,共三层(根节点所在的层记为0) class bulidfullsubtree { public static int treenodenum = 0;//满二叉树节点总数 public int noleafnode = 0;//满二叉树出去叶子节点外所剩余的非叶子节点 public static treenode[] treenode;//存储满二叉树所有节点的数组 public bulidfullsubtree(int nodenum) { treenodenum = convert.toint32(math.pow(2,nodenum+1)-1); noleafnode = convert.toint32(treenodenum - math.pow(2,nodenum)); treenode = new treenode[treenodenum]; for (int i = 0; i < treenodenum; i++) { treenode[i] = new treenode(i.tostring()); //对二叉树的所有节点初始化 } for (int i = 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 (int i = 1; i <= 2; i++) { treenode[i].level = 1; } for (int i = 3; i <= 6; i++) { treenode[i].level = 2; } for (int i = 7; i <= 14; i++) { treenode[i].level = 3; } } } //利用回溯法寻找最优解的类 class dealbagproblem { public treenode[] treenode = bulidfullsubtree.treenode; //获取建立好的二叉树 int maxweiht = 0;//背包最大承重量 int treelevel =convert.toint32(math.floor(math.log(bulidfullsubtree.treenodenum,2)))+1; //二叉树的最大层数 int []optionw=new int[100];//存储最优解的数组 int[] optionv = new int[100];//存储最优解的数组 int i = 0;//计数器,记录相应数组的下标 int midtw = 0;//中间变量,存储程序回溯过程中的中间值 int midtv = 0;//中间变量,存储程序回溯过程中的中间值 int midtw1 = 0;//中间变量,存储程序回溯过程中的中间值 int midtv2 = 0;//中间变量,存储程序回溯过程中的中间值 bagnode[] bagnode;//存储货物节点 string[] solution=new string[3]; //程序最终所得的最优解,分别存储:最优价值,总重量,路径 // int[] bestway=new int[100]; tracenode[] optiontrace=new tracenode[100];//存储路径路径 public dealbagproblem(bagnode[] bagn,treenode[] treenode,int maxw) { bagnode = bagn; maxweiht = maxw; for (int i = 0; i < optiontrace.length; i++) { //将路径数组对象初始化 optiontrace[i] = new tracenode(); } } //核心算法,进行回溯 //cursor:二叉树下一个节点的指针;tw:当前背包的重量;tv:当前背包的总价值 public void backtrace(treenode cursor,int tw,int tv) { 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; } } } //从所得到的临时解数组中找到最优解 public string[] findbestsolution() { int bestvalue=-1;//最大价值 int bestweight = -1;//与最大价值对应的重量 int bestmark = -1;//最优解所对应得数组编号(由i确定) for (int i = 0; i < optionv.length; i++) { if (optionv[i] > bestvalue) { bestvalue=optionv[i]; bestmark = i; } } bestweight=optionw[bestmark];//重量应该与最优解的数组下标对应 for (int i = 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(); return solution; } } class program { static void main(string[] args) { //测试数据(货物) //node[] bagnode = new node[100]; //bagnode bagnode1 = new bagnode(0, 5, 4); //bagnode bagnode2 = new bagnode(1, 3, 4); //bagnode bagnode3 = new bagnode(2, 2, 3); //测试数据(货物) bagnode bagnode1 = new bagnode(0, 16, 45); bagnode bagnode2 = new bagnode(1, 15, 25); bagnode bagnode3 = new bagnode(2, 15, 25); bagnode[] bagnodearr = new bagnode[] {bagnode1,bagnode2,bagnode3}; bulidfullsubtree bfs = new bulidfullsubtree(3); //第3个参数为背包的承重 dealbagproblem dbp = new dealbagproblem(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 (int i = 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("程序没有找到最优解,请检查你输入的数据是否合适!"); } } } //存储选择回溯路径的节点 public class tracenode { public int mark;//路径编号 public string tracestr;//所走过的路径(1代表取,2代表舍) public tracenode(int m,string t) { mark = m; tracestr = t; } public tracenode() { mark = -1; tracestr = ""; } } //回溯所要依附的满二叉树 class treenode { public treenode left;//左孩子指针 public treenode right;//右孩子指针 public int level;//数的层,层数代表货物的标识 string symb;//节点的标识,用其所在数组中的下标,如:“1”,“2” public bool bleftnode;//当前节点是否是父节点的左孩子 public treenode(treenode l, treenode r, int lev,string sb,bool ln) { left = l; right = r; level = lev; symb = sb; bleftnode = ln; } public treenode(string sb) { symb = sb; } } }
希望本文所述对大家的c#程序设计有所帮助。