第2关：装载问题 (最优队列法)

问题描述
任务描述
相关知识
编程要求
测试说明
问题描述
有一批共个集装箱要装上 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]; // 最优选择的物品组合Queue<QNode> 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;}
}