装载问题 | 分支限界法（限上界）

喜欢ヅ旅行 2023-02-10 01:02 20阅读 0赞

> **装载问题：**有n个集装箱要装上 2 艘载**重量分别为c1和c2的**轮船，**其中集装箱i的重量为wi**，且∑wi <= c1 + c2。
> 
> 问是否有一个合理的装载方案,可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。

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

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

--------------------

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

--------------------

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

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

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

--------------------

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

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

--------------------

**注意：**

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70][]

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

--------------------

### 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;
    }

[_ _01]: https://blog.csdn.net/weixin_43787043/article/details/105815795
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200519161130578.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw==,size_16,color_FFFFFF,t_70