C#使用回溯法解决背包问题实例分析
本文实例讲述了C#使用回溯法解决背包问题的方法。分享给大家供大家参考。具体如下：
背包问题描述：
给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高
实现代码：
usingSystem;
usingSystem.Collections.Generic;
usingSystem.Text;
namespaceBackRack
{
//要装入书包的货物节点
classBagNode
{
publicintmark;//货物编号，从0开始记
publicintweight;//货物重量
publicintvalue;//货物价值
publicBagNode(intm,intw,intv)
{
mark=m;
weight=w;
value=v;
}
}
//根据货物的数目，建立相应的满二叉树，如：3个货物，需要建立15个节点的二叉树，共三层（根节点所在的层记为0）
classBulidFullSubTree
{
publicstaticinttreeNodeNum=0;//满二叉树节点总数
publicintnoleafNode=0;//满二叉树出去叶子节点外所剩余的非叶子节点
publicstaticTreeNode[]treeNode;//存储满二叉树所有节点的数组
publicBulidFullSubTree(intnodeNum)
{
treeNodeNum=Convert.ToInt32(Math.Pow(2,nodeNum+1)-1);
noleafNode=Convert.ToInt32(treeNodeNum-Math.Pow(2,nodeNum));
treeNode=newTreeNode[treeNodeNum];
for(inti=0;i<treeNodeNum;i++)
{
treeNode[i]=newTreeNode(i.ToString());
//对二叉树的所有节点初始化
}
for(inti=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(inti=1;i<=2;i++)
{
treeNode[i].level=1;
}
for(inti=3;i<=6;i++)
{
treeNode[i].level=2;
}
for(inti=7;i<=14;i++)
{
treeNode[i].level=3;
}
}
}
//利用回溯法寻找最优解的类
classDealBagProblem
{
publicTreeNode[]treeNode=BulidFullSubTree.treeNode;
//获取建立好的二叉树
intmaxWeiht=0;//背包最大承重量
inttreeLevel=Convert.ToInt32(Math.Floor(Math.Log(BulidFullSubTree.treeNodeNum,2)))+1;
//二叉树的最大层数
int[]optionW=newint[100];//存储最优解的数组
int[]optionV=newint[100];//存储最优解的数组
inti=0;//计数器，记录相应数组的下标
intmidTw=0;//中间变量，存储程序回溯过程中的中间值
intmidTv=0;//中间变量，存储程序回溯过程中的中间值
intmidTw1=0;//中间变量，存储程序回溯过程中的中间值
intmidTv2=0;//中间变量，存储程序回溯过程中的中间值
BagNode[]bagNode;//存储货物节点
string[]solution=newstring[3];
//程序最终所得的最优解，分别存储：最优价值，总重量，路径
//int[]bestWay=newint[100];
TraceNode[]Optiontrace=newTraceNode[100];//存储路径路径
publicDealBagProblem(BagNode[]bagN,TreeNode[]treeNode,intmaxW)
{
bagNode=bagN;
maxWeiht=maxW;
for(inti=0;i<Optiontrace.Length;i++)
{
//将路径数组对象初始化
Optiontrace[i]=newTraceNode();
}
}
//核心算法，进行回溯
//cursor:二叉树下一个节点的指针;tw：当前背包的重量；tv：当前背包的总价值
publicvoidBackTrace(TreeNodecursor,inttw,inttv)
{
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;
}
}
}
//从所得到的临时解数组中找到最优解
publicstring[]FindBestSolution()
{
intbestValue=-1;//最大价值
intbestWeight=-1;//与最大价值对应的重量
intbestMark=-1;//最优解所对应得数组编号（由i确定）
for(inti=0;i<optionV.Length;i++)
{
if(optionV[i]>bestValue)
{
bestValue=optionV[i];
bestMark=i;
}
}
bestWeight=optionW[bestMark];//重量应该与最优解的数组下标对应
for(inti=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();
returnsolution;
}
}
classProgram
{
staticvoidMain(string[]args)
{
//测试数据（货物）
//Node[]bagNode=newNode[100];
//BagNodebagNode1=newBagNode(0,5,4);
//BagNodebagNode2=newBagNode(1,3,4);
//BagNodebagNode3=newBagNode(2,2,3);
//测试数据（货物）
BagNodebagNode1=newBagNode(0,16,45);
BagNodebagNode2=newBagNode(1,15,25);
BagNodebagNode3=newBagNode(2,15,25);
BagNode[]bagNodeArr=newBagNode[]{bagNode1,bagNode2,bagNode3};
BulidFullSubTreebfs=newBulidFullSubTree(3);
//第3个参数为背包的承重
DealBagProblemdbp=newDealBagProblem(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(inti=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("程序没有找到最优解，请检查你输入的数据是否合适！");
}
}
}
//存储选择回溯路径的节点
publicclassTraceNode
{
publicintmark;//路径编号
publicstringtraceStr;//所走过的路径（1代表取，2代表舍）
publicTraceNode(intm,stringt)
{
mark=m;
traceStr=t;
}
publicTraceNode()
{
mark=-1;
traceStr="";
}
}
//回溯所要依附的满二叉树
classTreeNode
{
publicTreeNodeleft;//左孩子指针
publicTreeNoderight;//右孩子指针
publicintlevel;//数的层，层数代表货物的标识
stringsymb;//节点的标识，用其所在数组中的下标，如：“1”，“2”
publicboolbLeftNode;//当前节点是否是父节点的左孩子
publicTreeNode(TreeNodel,TreeNoder,intlev,stringsb,boolln)
{
left=l;
right=r;
level=lev;
symb=sb;
bLeftNode=ln;
}
publicTreeNode(stringsb)
{
symb=sb;
}
}
}
希望本文所述对大家的C#程序设计有所帮助。