C#使用回溯法解决背包问题实例分析
更新时间:2020年6月25日 11:30 点击:1699
本文实例讲述了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#使用Socket上传并保存图片的方法
下一篇: C#线程池操作方法
相关文章
- 我们在使用C#做项目的时候,基本上都需要制作登录界面,那么今天我们就来一步步看看,如果简单的实现登录界面呢,本文给出2个例子,由简入难,希望大家能够喜欢。...2020-06-25
- 这篇文章主要介绍了C# 字段和属性的的相关资料,文中示例代码非常详细,供大家参考和学习,感兴趣的朋友可以了解下...2020-11-03
- 这篇文章主要介绍了C#中截取字符串的的基本方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-11-03
- 本文给大家分享C#连接SQL数据库和查询数据功能的操作技巧,本文通过图文并茂的形式给大家介绍的非常详细,需要的朋友参考下吧...2021-05-17
- 这篇文章主要介绍了C#实现简单的Http请求的方法,以实例形式较为详细的分析了C#实现Http请求的具体方法,需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C#中new的几种用法,具有很好的参考价值,下面跟着小编一起来看下吧...2020-06-25
使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序)
这篇文章主要介绍了使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序),小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25- 这篇文章主要介绍了C#开发Windows窗体应用程序的简单操作步骤,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-04-12
- 这篇文章主要介绍了C#从数据库读取图片并保存的方法,帮助大家更好的理解和使用c#,感兴趣的朋友可以了解下...2021-01-16
- 最近做一个小项目不可避免的需要前端脚本与后台进行交互。由于是在asp.net中实现,故问题演化成asp.net中jiavascript与后台c#如何进行交互。...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 轻松学习C#的基础入门,了解C#最基本的知识点,C#是一种简洁的,类型安全的一种完全面向对象的开发语言,是Microsoft专门基于.NET Framework平台开发的而量身定做的高级程序设计语言,需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C#变量命名规则小结,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-09-09
- 这篇文章主要介绍了c#中(&&,||)与(&,|)的区别详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 这篇文章主要介绍了C#绘制曲线图的方法,以完整实例形式较为详细的分析了C#进行曲线绘制的具体步骤与相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C# 中取绝对值的函数。具有很好的参考价值。下面跟着小编一起来看下吧...2020-06-25
- 这篇文章主要介绍了c#自带缓存使用方法,包括获取数据缓存、设置数据缓存、移除指定数据缓存等方法,需要的朋友可以参考下...2020-06-25
- 下面小编就为大家带来一篇C#学习笔记- 随机函数Random()的用法详解。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25
- 这篇文章主要介绍了C#中list用法,结合实例形式分析了C#中list排序、运算、转换等常见操作技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25