分支界定法(branch and bound)与背包问题的代码实现

LastEditTime: - 2021.2.3

---

不卖茶的吴龙茗茶

分支界定法是一种在整数规划中常用的算法，其主要思想为将大问题分割成小问题进行求解。分支界定法是围绕着一个二叉树进行的，以背包问题为例：

假设小明有一个背包，其总的容积为30，小明有三件东西可以带，三件东西的体积分别为：10,15,20。求问小明如何能够在背包中装下更大体积的物品？

我们建立一个长度为三的数组，元素大小分别为10,15,20。然后利用二叉树帮助我们解决问题

一个满二叉树应该是如下图所示

我们首先根据是否将第一个物品放入背包中进行分类（在这个二叉树中，左孩子一律为放入背包，右孩子一律为不放入背包），然后讨论第二个物品是否放入背包，以此类推。圆圈中的数字表明了放入背包的东西的总体积。

但是在分支界定法中引入了剪枝的操作，也就是在创造二叉树时，我们会对节点进行判断，如果节点的值，加上剩下的所有物品的容量的值比现在算出来能够装入背包最大的容量还要大，那么我们就对该节点进行剪枝，即在二叉树中不生成此节点。进行了剪枝之后的二叉树如下如图所示：

红色部分为被剪枝的部分。

FIFO分支界定法求解背包问题（c++实现）：

#include <iostream>
#include <list>
#include "limits.h"
using namespace std;

int main(){
    int best =0; int depth = 0;
    int par_val = 0; int cur_val = 0;
    int capacity = 30;
    int box[] = {10,15,20};
    list<int> myqueue;
    myqueue.push_back(0);
    //sizeof(box)/sizeof(box[0]为数组box的长度，在这里为3
    while(depth < sizeof(box)/sizeof(box[0]) && myqueue.size() != 0 ){
        //check left child
        par_val = myqueue.front();
        cur_val = par_val + box[depth];
        if(cur_val > best && cur_val <= capacity){
            best = cur_val;
        }
        myqueue.push_back(cur_val);

        //check right child
        cur_val = par_val;
        int rest = cur_val; 
        //判断余下的体积和现在算出来的best哪个大
        for(int i = depth + 1; i < sizeof(box)/sizeof(box[0]); i++){
            rest += box[i];
        }
        //剪枝判断，如果进行剪枝则加入一个负无穷，方便判断该层是否结束
        if(best < rest){
            myqueue.push_back(cur_val);
        }else{
            myqueue.push_back(INT_MIN);
        }
        myqueue.pop_front();
        //根据是否为2^n来判断该层是否结束
        if( (myqueue.size() & myqueue.size() - 1) == 0){
            depth++;
        }
    }
    cout << "best: " << best <<"\n";
}

运行结果：

Reference:

①：https://blog.csdn.net/yinlili2010/article/details/39313035