C#使用回溯法解決背包問題實例分析

2020-01-24 01:57:55

字體：大中小

來源：轉載

供稿：網友

本文實例講述了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#程序設計有所幫助。

上一篇：C#使用動態規劃解決0-1背包問題實例分析

下一篇：C#約瑟夫問題解決方法