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;  } }}