装载问题 | 分支界限法

装载问题：有n个集装箱要装上 2 艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且∑wi <= c1 + c2。

问是否有一个合理的装载方案,可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。

题目分析：其实就可以理解为，先装第一艘船，再装第二艘船，是否可以将货物全部装上，并给出解决方案。

主要待考虑的就是如何去装第一艘船？这个问题解决了后，剩下的都放入第二艘船即可。

---

       之前讨论过装载问题，传送门：装载问题 | 回溯：01选择（最大剪枝）。其中讨论了装载问题与最优装载问题的对比，本题不可以用贪心算法！这里不再赘述。其实从上文可见，回溯就是对所有方案进行 dfs，且中途剪枝优化。这里的分支界限法则是对所有方案进行 bfs，每次总是从最优点开始搜索。

---

1、选择树的分支界限算法

       理解了回溯算法中的枚举精髓（选择树），再来使用分支界限就很容易了。这里不再对细节进行阐述，只是将回溯的 dfs 改成 bfs 即可。细节讨论见装载问题 | 回溯：01选择（最大剪枝）。

      下面是决策树的模型，其中待讨论的节点应该保存在一个关键字位 key 的优先队列中。每次取出 key 最大的节点继续讨论。

---

    这里最重要的是注意对每一个节点的理解：

• 节点应该是一种决策方案的运行到某一位置的结果保存
• 节点中应该有：cur_w（当前船上重量）、r（剩余未选择物品的总重量）、关键字key（cur_w + r）、step（下一个应选取得物品标号）
• 当节点被取出时，应该节点保存的数据状态下继续讨论：是否放第 step 个物品，有两种选择。把合适的抉择子节点继续添加到优先队列中     

---

注意：

1. 我们的物品各个重量储存在数组 w 中，从0开始。故当节点中的 step = n 时，说明该节点就是叶子节点了，已经决策完毕！
2. 关键字key其实也就是，这个节点存在的决策线路最终答案的上界！

        这个分支界限法已经进行了优化剪枝，其中已经加了：约束条件、限界条件。所以上图有一些决策点是被省略的！ 

---

2、代码实现

#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

typedef struct node {
    int key;     //key = cur_w + r,关键字：上界
    int cur_w;   //当前船上的重量
    int r;       //未选择货物的剩余总重
    int step = 0;  //当前搜索的层数（在讨论哪个物品）

    /* 构造函数 */
    node(int k, int cw, int r, int s) {
        key = k;
        cur_w = cw;
        this->r = r;
        step = s;
    }

    /* 重载 struct node 的比较运算符
     *  方便后面建立优先队列的大小定位 */
    friend bool operator<(struct node x, struct node y) {
        return x.key < y.key;
    }
} Node;

int best_w = 0;

int w[100];  //待选物品的重量
int n;  //题中待选物品的数量
int c; //船的最大载重

int cur_w = 0;  //当前船上的重量
int r;  //当前待选物品的总重量
int step;  //当前层数

void bfs() {
    priority_queue<Node> Q;   //定义一个优先队列
    Node head(r, 0, r, 0);  //从根节点开始遍历

    /* 当遍历到叶节点（每一件货物都讨论了）就结束 */
    while (head.step <= n) {

        step = head.step;
        cur_w = head.cur_w;
        r = head.r - w[step];  //对于剩余货物总重来说，加不加都要减去当前货物
        int maybe = cur_w + w[step]; //如果加上当前货物，船上将有重量

        /* 选择当前物品 （满足约束条件）*/
        if (maybe <= c) {
            best_w = max(best_w, maybe);  //更新最优值
            Node temp(maybe + r, maybe, r, step + 1);
            Q.push(temp);
        }
        /* 不选择当前物品 （满足限界条件）*/
        if (head.key > best_w) {
            Node temp(cur_w + r, cur_w, r, step + 1);
            Q.push(temp);
        }

        /* 出队key最大的 */
        head = Q.top();
        Q.pop();
    }
}

int main() {
    w[0] = 16;
    w[1] = 15;
    w[2] = 15;
    r = 16 + 15 + 15;
    c = 30;
    n = 3;

    bfs();
    cout << best_w << endl;
}