C#應用回溯法處理背包成績實例剖析。本站提示廣大學習愛好者：（C#應用回溯法處理背包成績實例剖析）文章只能為提供參考，不一定能成為您想要的結果。以下是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#法式設計有所贊助。
