欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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#程序设计有所帮助。