实验六 回溯算法

《实验六 回溯算法》由会员分享，可在线阅读，更多相关《实验六 回溯算法（5页珍藏版）》请在装配图网上搜索。

1、实验六 回溯算法(2 学时)一、实验目的与要求1、掌握装载问题的回溯算法；2、初步掌握回溯算法；二、实验题有一批共n个集装箱要装上2艘载重量分别为cl和c2的轮船，其中集装箱i的重量为 wi,且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果 有，找出一种装载方案三、实验提示void backtrack (int i)搜索第i层结点if (i n) /到达叶结点更新最优解 bestx,bestw;return;r -= wi;if (cw + wi bestw) xi = 0; / 搜索右子树 backtrack(i + l);r += wi;四、程序代码解题思路：(

2、1) 首先将第一艘轮船尽可能装满。(2) 然后将剩余的集装箱装上第二艘轮船。 将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近 cl。class teststatic int n;static int weight;static static static static staticint limitWeight; int currentweight; int bestWeight; int remainWeight; int x;最小最优载重星当前载重星当前最优载重星剩余载重星static int bestz;public static int maxLo

3、ading(int weightArray, int clWeight, out int _x)n = weightArray.Length - 1: weight = weightArray; limitWeight = clWeight; currentweight = 0: bestWeight = 0;x = new intn + 1；= new intn + 1;bestx = _x:foreach (int elem in weight) remainWeight 十=elm;backtrack(0): wturn bestWeight;private static void ba

4、cktraLck(iirt i)if (i n)i (currentWeight bestWeight)x. Copy To (bes tz, 0):bestWeight = currentWeight;ret urn;remainWeight -= weighti;if (currentWeight + weighti best Weight) xi = 0;back track (i + 1);remainWeight 4= weight i;class Programstatic void Main(string args)int w= new int 10, 25, 35, 45, 5

5、5, 65, 75, 95, 105, 150 ;int cl = 600 :AZ假设cl的重里药6DDint c2 = 300; 假设c2的重 1.5600int x;int bestel = test.maxLoading(w, cl, out x);int weight = 0;foreach (int elem in w)weight += elem;if (c2 weight - bestcl)Console.WriteLine(无解。;|return;Console. WriteLine (cl可装载0 , bestcl);Console. WriteLine (cl包含集装箱:”

6、)；for (int i = 0; i x Length; i+) if (xi = 1)Console. Write 0 ”，i + 1);Console VfriteLine ();Console VfriteLine ();Console. WriteLine (c2可装载0, weight - bestcl);Console. WriteLine (c2包含集装箱:”)；for (int i = 0; i x Length; i+)if (xi = 0)Console. Write 0 ”，i + 1);Console VfriteLine ();Console Read();五、实验结果六、实验总结装载问题属于多选择问题，符合回溯法的特点。通过本次集装箱问题实验，我学会了如 何使用回溯算法解决实际问题，并初步掌握装载问题的回溯算法，了解了回溯法的基本思想 和解题思路。实验后，我会继续学习，理解回溯算法思想，做到可以独立利用回溯法解决问 题。