注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

C#回溯法解决背包问题

OC/C/C++ 水墨上仙 2293次浏览 已收录 手机上查看

C#回溯法解决背包问题转自:http://hi.baidu.com/y_x_b_s/item/8c518a1c1eb970446926bbb3

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#回溯法解决背包问题
喜欢 (0)
[开心洋葱]
分享 (0)
关于作者:
水墨上仙
……
加载中……