問題描述
任務描述
相關知識
編程要求
測試說明
問題描述
有一批共個集裝箱要裝上 2 艘載重量分別為 C1 和 C2 的輪船，其中集
裝箱i的重量為 Wi ，且
裝載問題要求確定是否有一個合理的裝載方案可將這個集裝箱裝上這 2 艘輪船。如果有，找出一種裝載方案。

容易證明：如果一個給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。

(1)首先將第一艘輪船盡可能裝滿；

(2)將剩余的集裝箱裝上第二艘輪船。

任務描述
本關任務：采用優(yōu)先隊列式分支限界法來完成裝載問題

相關知識
1，解裝載問題的優(yōu)先隊列式分支限界法用最大優(yōu)先隊列存儲活結(jié)點表?；罱Y(jié)點 x 在優(yōu)先隊列中的優(yōu)先級定義為從根結(jié)點到結(jié)點x的路徑所相應的載重量再加上剩余集裝箱的重量之和。

2，優(yōu)先隊列中優(yōu)先級最大的活結(jié)點成為下一個擴展結(jié)點。以結(jié)點 x 為根的子樹中所有結(jié)點相應的路徑的載重量不超過它的優(yōu)先級。子集樹中葉結(jié)點所相應的載重量與其優(yōu)先級相同。

3，在優(yōu)先隊列式分支限界法中，一旦有一個葉結(jié)點成為當前擴展結(jié)點，則可以斷言該葉結(jié)點所相應的解即為最優(yōu)解。此時可終止算法。

編程要求
請仔細閱讀右側(cè)代碼，結(jié)合相關知識，在 Begin - End 區(qū)域內(nèi)進行代碼補充，完成采用優(yōu)先隊列式分支限界法來完成裝載問題的任務。

測試說明
平臺會對你編寫的代碼進行測試：

測試輸入：
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 {// 定義一個內(nèi)部類 QNode，表示隊列中的節(jié)點class QNode {int level; // 當前處理的物品層級（即第幾個物品）int weight; // 當前已選擇的物品總重量boolean[] selection; // 當前選擇的物品組合// QNode 構(gòu)造函數(shù)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(); // 讀取物品數(shù)量int shipWeight = input.nextInt(); // 讀取船的最大載重量int[] goods = new int[num]; // 創(chuàng)建一個數(shù)組來存儲物品的重量// 讀取每個物品的重量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();// 創(chuàng)建主類的實例并調(diào)用 loadGoods 方法MaxLoading_2 mainInstance = new MaxLoading_2();mainInstance.loadGoods(goods, shipWeight);}// 加載物品的方法public void loadGoods(int[] goods, int shipWeight) {int num = goods.length; // 物品數(shù)量int maxWeight = 0; // 當前最優(yōu)的載重量boolean[] bestSelection = new boolean[num]; // 最優(yōu)選擇的物品組合Queue<QNode> queue = new LinkedList<>(); // 創(chuàng)建一個隊列來存儲節(jié)點boolean[] initialSelection = new boolean[num]; // 初始化選擇的物品組合queue.add(new QNode(0, 0, initialSelection)); // 將初始節(jié)點加入隊列// 當隊列不為空時，繼續(xù)處理while (!queue.isEmpty()) {QNode currentNode = queue.poll(); // 取出隊列中的第一個節(jié)點// 如果當前節(jié)點已經(jīng)處理完所有物品if (currentNode.level == num) {// 如果當前節(jié)點的總重量小于等于船的最大載重量，并且比當前最優(yōu)載重量大if (currentNode.weight <= shipWeight && currentNode.weight >= maxWeight) {if (currentNode.weight > maxWeight || isCloserToTarget(currentNode.selection, bestSelection)) {maxWeight = currentNode.weight; // 更新最優(yōu)載重量bestSelection = currentNode.selection; // 更新最優(yōu)選擇的物品組合}}continue; // 繼續(xù)處理下一個節(jié)點}// 如果選擇當前物品后總重量不超過船的最大載重量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)); // 將新節(jié)點加入隊列}// 不選擇當前物品boolean[] newSelection = currentNode.selection.clone(); // 復制當前選擇的物品組合newSelection[currentNode.level] = false; // 不選擇當前物品queue.add(new QNode(currentNode.level + 1, currentNode.weight, newSelection)); // 將新節(jié)點加入隊列}// 輸出結(jié)果System.out.println("Result:");for (int i = 0; i < num; i++) {System.out.print((bestSelection[i] ? 1 : 0) + " "); // 輸出最優(yōu)選擇的物品組合}System.out.println();System.out.println("The optimal loading weight is:" + maxWeight); // 輸出最優(yōu)載重量}// 判斷給定的選擇是否更接近目標選擇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;}
}