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;
}
}
}
//csharp/7207