装载问题的回溯算法实现(共4页).doc

《装载问题的回溯算法实现(共4页).doc》由会员分享，可在线阅读，更多相关《装载问题的回溯算法实现(共4页).doc（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上装载问题的回溯算法实现实验报告一、实验目的通过本实验使学生掌握回溯算法基本要素、步骤及其应用二、实验原理本实验是应用回溯算法用Java编程语言对给定两艘轮船的载重量和一批集装箱，集装箱的重量之和小于等于两艘船的载重量之和。Java编程语言见Java 基础教程,装载问题的回溯算法见王晓东编算法设计与分析（第二版）p152-160.三、实验内容Java编程语言实现装载问题的回溯算法。主要实验内容包含：给定两艘轮船的载重量c1和c2，n个集装箱及其重量wn，确定合理的装载方案将n个集装箱装上这两艘船。四、使用仪器、材料myEclipse五、实验步骤1、给定轮船的载重量c1和

2、c2，集装箱数量n和集装箱重量的集合wn；2、用回溯算法将第一艘轮船尽可能装满；3、输出第一艘轮船的装载方案；4、输出第二艘船的装载方案。六、实验原始记录及其处理（数据、图表、计算等）package ts;public class Load static int n;static int w = 40, 50, 40, 30, 55 ; /第一个并没有使用/ static int ww ;static int c1, c2;static int cw;static int bestw;static int r;static int x;/ static int y;static int bes

3、tx;public static int maxLoading(int w, int cc, int xx) n = w.length - 1;cw = 0;bestw = 0;bestx = xx;for (int i = 0; i n) / 到达叶结点if (cw bestw) for (int j = 1; j = n; j+)bestxj = xj; / 更新最优解bestxbestw = cw; / 更新最优值bestwreturn;r -= wi;if (cw + wi bestw) xi = 0; / 搜索右子树backtrack(i + 1, cc);r += wi;publi

4、c static void main(String args) int k = 1;/int j = 0;c1 = 110;c2 = 100;x = new intw.length;maxLoading(w, c1, x);for (int i = 1; i x.length; i+) /总共只有四个集装箱 w0并没有用if (xi = 1) System.out.println(第 + (i) + 箱货物在第一次装入，装入顺序为+ (k+);for (int i = 1; i x.length; i+) if (xi = 0)System.out.println(第 + (i) + 箱货物在

5、第二次装入，装入顺序为+ (k+);/ ww=new intk;/ for (int i = 0; i k; i+) / if(xi=0)/ wwj+=wi;/ System.out.println(xi);/ / y=new intk;/ for (int i = 0; i y.length; i+) / if(xi=0) yi=xi;/ / System.out.println(y.length);/ maxLoading(ww, c2, y);七、实验结果及分析输入的信息如下：包括集装箱的重量w,1船2船的载重量c1,c2。输出的结果如下：主要步骤是用回溯法找出装入1船的最优装载方案，然后把剩下的货物一次装入2船中。注：w.length=5,但是在程序运行时是从w1开始的，所以w0，没有用，输出时只有四个集装箱。专心-专注-专业