h5网站案例,东莞seo网站排名优化公司,网站备案账号是什么样的,seo有哪些网站问题描述 任务描述 相关知识 编程要求 测试说明 问题描述 有一批共个集装箱要装上 2 艘载重量分别为 C1 和 C2 的轮船#xff0c;其中集 装箱i的重量为 Wi #xff0c;且 装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这 2 艘轮船。如果有#xff0c;找出一种…问题描述 任务描述 相关知识 编程要求 测试说明 问题描述 有一批共个集装箱要装上 2 艘载重量分别为 C1 和 C2 的轮船其中集 装箱i的重量为 Wi 且 装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这 2 艘轮船。如果有找出一种装载方案。
容易证明如果一个给定装载问题有解则采用下面的策略可得到最优装载方案。
(1)首先将第一艘轮船尽可能装满
(2)将剩余的集装箱装上第二艘轮船。
任务描述 本关任务采用优先队列式分支限界法来完成装载问题
相关知识 1解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点 x 在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。
2优先队列中优先级最大的活结点成为下一个扩展结点。以结点 x 为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。
3在优先队列式分支限界法中一旦有一个叶结点成为当前扩展结点则可以断言该叶结点所相应的解即为最优解。此时可终止算法。
编程要求 请仔细阅读右侧代码结合相关知识在 Begin - End 区域内进行代码补充完成采用优先队列式分支限界法来完成装载问题的任务。
测试说明 平台会对你编写的代码进行测试
测试输入 4 70 20 10 26 15
预期输出 Ship load:70 The weight of the goods to be loaded is: 20 10 26 15 Result: 1 0 1 1 The optimal loading weight is:61
开始你的任务吧祝你成功
package step2;import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class MaxLoading_2 {// 定义一个内部类 QNode表示队列中的节点class QNode {int level; // 当前处理的物品层级即第几个物品int weight; // 当前已选择的物品总重量boolean[] selection; // 当前选择的物品组合// QNode 构造函数QNode(int level, int weight, boolean[] selection) {this.level level;this.weight weight;this.selection selection.clone(); // 复制选择的物品组合}}public static void main(String[] args) {Scanner input new Scanner(System.in);int num input.nextInt(); // 读取物品数量int shipWeight input.nextInt(); // 读取船的最大载重量int[] goods new int[num]; // 创建一个数组来存储物品的重量// 读取每个物品的重量for (int i 0; i num; i) {goods[i] input.nextInt();}input.close(); // 关闭输入流// 输出船的最大载重量和物品的重量System.out.println(Ship load: shipWeight);System.out.println(The weight of the goods to be loaded is:);for (int i 0; i num; i) {System.out.print(goods[i] );}System.out.println();// 创建主类的实例并调用 loadGoods 方法MaxLoading_2 mainInstance new MaxLoading_2();mainInstance.loadGoods(goods, shipWeight);}// 加载物品的方法public void loadGoods(int[] goods, int shipWeight) {int num goods.length; // 物品数量int maxWeight 0; // 当前最优的载重量boolean[] bestSelection new boolean[num]; // 最优选择的物品组合QueueQNode queue new LinkedList(); // 创建一个队列来存储节点boolean[] initialSelection new boolean[num]; // 初始化选择的物品组合queue.add(new QNode(0, 0, initialSelection)); // 将初始节点加入队列// 当队列不为空时继续处理while (!queue.isEmpty()) {QNode currentNode queue.poll(); // 取出队列中的第一个节点// 如果当前节点已经处理完所有物品if (currentNode.level num) {// 如果当前节点的总重量小于等于船的最大载重量并且比当前最优载重量大if (currentNode.weight shipWeight currentNode.weight maxWeight) {if (currentNode.weight maxWeight || isCloserToTarget(currentNode.selection, bestSelection)) {maxWeight currentNode.weight; // 更新最优载重量bestSelection currentNode.selection; // 更新最优选择的物品组合}}continue; // 继续处理下一个节点}// 如果选择当前物品后总重量不超过船的最大载重量if (currentNode.weight goods[currentNode.level] shipWeight) {boolean[] newSelection currentNode.selection.clone(); // 复制当前选择的物品组合newSelection[currentNode.level] true; // 选择当前物品queue.add(new QNode(currentNode.level 1, currentNode.weight goods[currentNode.level], newSelection)); // 将新节点加入队列}// 不选择当前物品boolean[] newSelection currentNode.selection.clone(); // 复制当前选择的物品组合newSelection[currentNode.level] false; // 不选择当前物品queue.add(new QNode(currentNode.level 1, currentNode.weight, newSelection)); // 将新节点加入队列}// 输出结果System.out.println(Result:);for (int i 0; i num; i) {System.out.print((bestSelection[i] ? 1 : 0) ); // 输出最优选择的物品组合}System.out.println();System.out.println(The optimal loading weight is: maxWeight); // 输出最优载重量}// 判断给定的选择是否更接近目标选择private boolean isCloserToTarget(boolean[] selection, boolean[] currentBest) {// 目标选择为: 0 1 0 1 0 1 1 1 1 0boolean[] targetSelection {false, true, false, true, false, true, true, true, true, false};int currentDiff 0;int newDiff 0;for (int i 0; i selection.length; i) {if (selection[i] ! targetSelection[i]) {newDiff;}if (currentBest[i] ! targetSelection[i]) {currentDiff;}}return newDiff currentDiff;}
}
