前面我們介紹了一下回溯法的使用，

現在我們來給大家介紹一下它的好朋友——分支界限法，

如果說回溯法是使用深度優先遍歷演算法，那么分支界限法就是使用廣度優先遍歷演算法，

深度優先遍歷可以只使用一個屬性來存放當前狀態，但是廣度優先遍歷就不可以了，所以廣度優先遍歷的節點必須用來存盤當前狀態，一個節點代表一個當前狀態，而一條邊就代表了一次操作，A狀態經過一條邊（操作）變為B狀態，

我在寫這篇文章的時候搜遍了網上各種各樣的分支界限法來解決01背包問題，看各個代碼都要一兩百行，都是優化之后的最優化版分支界限法，這樣是不利于新手進行理解的，所以我在此寫了一個最初級的分支界限法解決01背包問題，可以看到要不了50行就能解決01背包問題，

分支界限法

對于分支界限法，網上有很多種解釋，這里我依照自己的（死宅）觀點做了以下兩種通俗易懂的解釋：

正經版解釋：所謂“分支”就是采用廣度優先的策略，依次搜索E-結點的所有分支，也就是所有相鄰結點，拋棄不滿足約束條件的結點，其余結點加入活結點表，然后從表中選擇一個結點作為下一個E-結點，繼續搜索，
動漫版解釋：看過火影忍者的都知道，主角擁有影分身的能力，如果主角使用影分身從一個點出發，前往不同的分支，主角的運動速度相同的情況下，同一時刻時分支的深度也應該相同，有的分身走到死路，有的分身達到界限無法進行下去，當分身無法進行下去時，那么就解除該分身，直接放棄掉這個分身，當然，肯定也會有分身成功到達目的地找到最優解，這與我們今天要講的分支界限法極其相似，

PS：雛田黨大獲全勝！

總結版解釋：從眾多分支的路徑中，同時地毯式搜索找到符合結果的路徑或路徑集，

概念

分支界限演算法：是類似于廣度優先的搜索程序，也就是地毯式搜索，主要是在搜索程序中尋找問題的解，當發現已不滿足求解條件時，就舍棄該分身，不管了，
它是一種選優搜索法，按選優條件向前廣度優先搜索，以達到目標，但當探索到某一步時，發現原先選擇并不優或達不到目標，就放棄該分身，不進行下一步退回，這種走不通就放棄分身的技術稱為分支界限法，

所謂“分支”就是采用廣度優先的策略，依次搜索E-結點的所有分支，也就是所有相鄰結點，拋棄不滿足約束條件的結點，其余結點加入活結點表，然后從表中選擇一個結點作為下一個E-結點，繼續搜索，

選擇下一個E-結點的方式不同，則會有幾種不同的分支搜索方式，不用感到恐慌，其實這幾種不同的搜索方式很好實作，只需要換一下不同的資料結構容器即可，

FIFO搜索（使用佇列實作）：按照先進先出原則選取下一個節點為擴展節點，活結點表是先進先出佇列，
LIFO搜索（使用堆疊實作）：活結點表是堆疊，
優先佇列式搜索（使用優先佇列實作）：按照優先佇列中規定的優先級選取優先級最高的節點成為當前擴展節點，活結點表是優先權佇列，LC分支限界法將選取具有最高優先級的活結點出佇列，成為新的E-結點，

Java中的優先佇列PriorityQueue對元素采用的是堆排序，頭是按指定排序方式的最小元素，堆排序只能保證根是最大（最小），整個堆并不是有序的，
優先佇列PriorityQueue是Queue介面的實作，可以對其中元素進行排序，可以放基本的包裝型別或自定義的類，對于基本型別的包裝類，優先佇列中元素的默認排列順序是升序，但是對于自定義類來說，需要自定義比較類

上圖為01背包問題的解空間樹，如果當前點不符合要求就放棄，直接剪枝，
在許多能使用回溯法的問題時，都可以使用分支界限法，算是給讀者一個新的思路去解決問題，

基本思想

在包含問題的所有解的解空間樹中，按照廣度優先搜索的策略，從根結點出發廣度地毯式探索解空間樹，對于不同的分支搜索方式要使用不同的資料結構來實作，
當探索到某一結點時，要先判斷該結點是否包含問題的解：

如果包含，就將該結點的延伸結點加入佇列，以便之后遍歷；
如果該結點不包含問題的解，則直接剪枝放棄該結點的延伸結點，（其實分子界限法就是對隱式圖的廣度優先搜索演算法）

結束條件：

若用分子界限法求問題的所有解時，根結點的所有可行的子樹都要已被搜索遍才結束，
若使用分子界限法求任一個解時，只要搜索到問題的一個解就可以結束，

適用場景

分支界限法一般使用在問題可以樹形化表示時的場景，

這樣說明的話可能有點抽象，那么我們來換個方法說明，
當你發現，你的問題需要用到多重回圈，具體幾重回圈你又沒辦法確定，那么就可以使用我們的分支界限演算法來將回圈一層一層的進行遍歷，

就像這樣：

void LevelOrder(BiTree T) {
    InitQueue(Q);       //初始化輔助佇列
    BiTNode *p;
    EnQueue(Q, T);      //將根結點入隊
    while(!IsEmpty(Q)) {    //佇列不慷訓圈
        DeQueue(Q, p);      //隊頭元素出隊，出隊指標才是用來遍歷的遍歷指標
        visit(p);           //訪問當前p所指向結點
        if(p->lchild != NULL) { //左子樹不空，則左子樹入佇列
            EnQueue(Q, p->lchild);
        }
        if(p->rchild != NULL) { //右子樹不空，則右子樹入佇列
            EnQueue(Q, p->rchild);
        }
    }
}

這樣層次遍歷的話，無論多少重回圈我們都可以滿足，

分支界限三步走

由于上述網上的步驟太抽象了，所以在這里我自己總結了分子界限三步走：

撰寫檢測函式：檢測函式用來檢測此路徑是否滿足題目條件，是否能通過，

這步不做硬性要求，，不一定需要

建立狀態結點：分支界限法中需要廣度優先遍歷整個分支樹，所以其結點都需要記錄下當前的狀態，否則到需要進行遍歷時我們不能得知此結點的狀態，無法進行操作，

與此相對的就是回溯法，回溯法由于是一條路走到底，所以并不需要使用結點記錄下當前的狀態，
類比：做作業
回溯法：先做完數學作業再做英語作業，我們的思路是完整的，是一步一步順著來的，不會被遺忘，
分支界限法：做一會數學作業，再做一會英語作業，這樣我們為了保證之前做的思路不會遺忘，我們要使用結點記錄下當前的狀態，
明確所有分支（選擇）：這個構思路徑最好用樹形圖表示，

例如：走迷宮有上下左右四個方向，也就是說我們站在一個點處有四種選擇，我們可以畫成無限向下延伸的四叉樹，
直到向下延伸到葉子節點，那里便是出口；
從根節點到葉子節點沿途所經過的節點就是我們滿足題目條件的選擇，
尋找界限條件：每一個分支都需要進行判斷，判斷是否到達了界限，如果到達界限那么我們就無需再進行下去了，直接剪枝放棄該分支，

比如說，01背包中的界限條件就是，在將物品放置進背包前，要進行判斷放入背包是否會造成超重，如果不超重，那就可以放入背包，

撰寫檢測函式（非必須）

第一步，寫出檢測函式，來檢測這個路徑是否滿足條件，是否能通過，
這個函式依據題目要求來撰寫，當然，如果要求不止一個，可能需要撰寫多個檢測函式，

建立狀態結點

分支界限法中需要廣度優先遍歷整個分支樹，所以其結點都需要記錄下當前的狀態，否則到需要進行遍歷時我們不能得知此結點的狀態，無法進行操作，

與此相對的就是回溯法，回溯法由于是一條路走到底，所以并不需要使用結點記錄下當前的狀態，
類比：做作業
回溯法：先做完數學作業再做英語作業，我們的思路是完整的，是一步一步順著來的，不會被遺忘，
分支界限法：做一會數學作業，再做一會英語作業，這樣我們為了保證之前做的思路不會遺忘，我們要使用結點記錄下當前的狀態，

在01背包問題中，我們需要記錄的狀態是此時背包內物品的重量與價值，所以我們的狀態結點為：

/**
 * 結點類，一個結點物件對應著一個當前的背包狀態
 */
class Node {

    public int weight; // 結點所相應的重量
    public int value; // 結點所對應的價值

    public Node() {
    }

    public Node(int weight, int value) {
        this.weight = weight;
        this.value = https://www.cnblogs.com/blknemo/p/value;
    }
}

明確所有分支

這個構思路徑最好用樹形圖表示，

例如：走迷宮有上下左右四個方向，也就是說我們站在一個點處有四種選擇，我們可以畫成無限向下延伸的四叉樹，
直到向下延伸到葉子節點，那里便是出口；
從根節點到葉子節點沿途所經過的節點就是我們滿足題目條件的選擇，

第三步，要知道這個結點有幾個選擇，即幾叉樹，

在01背包問題中，每個物品都有2個選擇，0不放入背包，1放入背包，兩條路，二叉樹，

不放入背包
放入背包

尋找界限條件

每一個分支都需要進行判斷，判斷是否到達了界限，如果到達界限那么我們就無需再進行下去了，直接剪枝放棄該分支，

比如說，01背包中的界限條件就是，在將物品放置進背包前，要進行判斷放入背包是否會造成超重，如果不超重，那就可以放入背包，

前面我們確定了一個結點有兩條分支，一個是不裝入背包，一個是裝入背包，我們現在需要為每個分支尋找它們的界限條件，

不裝入背包當然沒有什么界限條件，而裝入背包則需要判斷，如果放入背包是否會造成超重，如果不超重，那就可以放入背包，

代碼如下：

// 不放此p號物品的狀態
queue.add(new Node(nowBagNode.weight, nowBagNode.value));

// 放置此p號物品的狀態
if (nowBagNode.weight + weights[p] < maxWeight) {

    nowBagNode.weight += weights[p];
    nowBagNode.value += values[p];
    p++;

    queue.add(new Node(nowBagNode.weight, nowBagNode.value));

    maxValue = https://www.cnblogs.com/blknemo/p/nowBagNode.value > maxValue? nowBagNode.value : maxValue;
}

完整的代碼我放在下面的實體中了，

實體

01背包問題

假定有N=4件商品，分別用A、B、C、D表示，每件商品的重量分別為3kg、2kg、5kg和4kg，對應的價值分別為66元、40元、95元和40元，現有一個背包，可以容納的總重量位9kg，問：如何挑選商品，使得背包里商品的總價值最大？

22、20、19、10

答案：
暴力破解法：

由于暴力破解法不是我們本章的重點，所以代碼再此掠過，只留下示意圖

/**
 * 結點類，一個結點物件對應著一個當前的背包狀態
 */
class Node {

    public int weight; // 結點所相應的重量
    public int value; // 結點所對應的價值

    public Node() {
    }

    public Node(int weight, int value) {
        this.weight = weight;
        this.value = https://www.cnblogs.com/blknemo/p/value;
    }
}

public class Bag01 {

    public int maxWeight = 9;   // 背包的最大容量
    public int maxValue = 0;    // 背包內的最大價值總和

    /**
     * 分支界限法
     * @param weights 所有物品的重量陣列
     * @param values 所有物品的價值陣列
     */
    public void f(int[] weights, int[] values) {

        Queue queue = new ArrayDeque<>();
        Node node = new Node();
        
        // 放入一個初始結點，結點狀態均為0
        queue.add(node);

        int p = 0;  // 物品指標位置

        while (!queue.isEmpty()) {
            // 取出當前結點的背包狀態
            Node nowBagNode = queue.remove();

            // 如果物品沒有放完
            if (p < weights.length) {
                // 不放此p號物品的狀態
                queue.add(new Node(nowBagNode.weight, nowBagNode.value));

                // 放置此p號物品的狀態，如果放入超重了，那就不能放
                if (nowBagNode.weight + weights[p] < maxWeight) {

                    nowBagNode.weight += weights[p];
                    nowBagNode.value += values[p];
                    p++;

                    queue.add(new Node(nowBagNode.weight, nowBagNode.value));

                    maxValue = nowBagNode.value > maxValue? nowBagNode.value : maxValue;
                }
            }
        }
        System.out.println(maxValue);
    }

    public static void main(String[] args) {
        
        int[] weights = {2, 3, 5, 4};
        int[] values = {66, 40, 95, 40};
        Bag01 bag01 = new Bag01();
        bag01.f(weights, values);
    }
}

程式運行結果：

如果你想換一種搜索方式，那么你可以把上面的佇列換成堆疊或者優先佇列試試，

優化

我還想看一下他們的代碼，寫一個優化版本，

上界估算優化

這里我們的上界估算是結合貪心演算法的優先佇列（剪枝）

這里我們還是拿01背包問題來舉例子，

需要注意的是，這里的優先佇列是一個人為的概念，你也可以指定屬于自己的優先級排列方式，只要言之有理，能讓速度加快即可，

結合貪心演算法，這里我們假設能夠只拿物品的一部分把背包塞滿，每次從佇列中取出上限值最大的一個結點（即從該結點出發到葉子節點在理想情況下可能得到的最大價值）

注意是“可能得到的最大價值”，真實情況下由于每件商品只能整體選擇或者不選，因此價值總和總是小于等于該最大上限值，而且隨著道路的不斷前進，該最優值總是不斷減小，越來越接近真實值，當走完全程考慮完所有商品時，該最優值就變成了真實值，

也就是說，價值上限=節點現有價值+背包剩余容量*剩余物品的最大單位重量價值

現在我們計算出它們的性價比，我們每次都選取單位重量下價值最大的那個物品，并且假定我們可以只選取物品的一部分，

商品	重量	價值	性價比
A	3	66	22
B	2	40	20
C	5	95	19
D	4	40	10

性價比：A>B>C>D

最大上限值的計算，就拿A結點來舉例好了：
第一步：如實計算已選道路：在此道路中A是必選的

選A，總重量3，總價值0+66=66

第二步：貪婪演算法計算未知道路，
我們依次選取出性價比最高的物品：

選A+B，總重量5，總價值66+40=106
選A+B+部分C，總重量9，106+4*19=182

所以A結點的上限為182，

遍歷方法：
我們每次都從優先佇列中取出上限值最大的一個結點，依次加入該結點的子節點進行遍歷，直到彈出的上限值（即最大最優價值）為某一葉子節點（即結果），此葉子節點即為獲得背包最大價值的最優組合方式，因為它比其他道路最優的情況還要好，那么它一定大于其他道路的真實價值，

物品類：

public class Knapsack implements Comparable<Knapsack> {
    /*物品重量*/
    private int weight;
    /*物品價值*/
    private int value;
    /*單位重量價值*/
    private int unitValue;

    public Knapsack(int weight, int value){
        this.weight = weight;
        this.value = https://www.cnblogs.com/blknemo/p/value;
        this.unitValue = (weight == 0) ? 0 : value/weight;
    }

    public int getWeight(){
        return weight;
    }

    public void setWeight(int weight){
        this.weight = weight;
    }

    public int getValue(){
        return value;
    }

    public void setValue(int value){
        this.value = value;
    }

    public int getUnitValue(){
        return unitValue;
    }

    @Override
    public int compareTo(Knapsack snapsack) {
        int value = snapsack.unitValue;
        if (unitValue > value)
            return 1;
        if (unitValue < value)
            return -1;
        return 0;
    }
}

當前狀態結點：

/*當前操作的節點，放入物品或不放入物品*/
class Node {
    /*當前放入物品的重量*/
    private int currWeight;
    /*當前放入物品的價值*/
    private int currValue;
    /*不放入當前物品可能得到的價值上限*/
    private int upperLimit;
    /*當前操作物品的索引*/
    private int index;
    public Node(int currWeight, int currValue, int index) {
        this.currWeight = currWeight;
        this.currValue = https://www.cnblogs.com/blknemo/p/currValue;
        this.index = index;
    }
}

實作：

public class ZeroAndOnePackage {

    /*物品陣列*/
    private Knapsack[] knapsacks;
    /*背包承重量*/
    private int totalWeight;
    /*物品數*/
    private int num;
    /*可以獲得的最大價值*/
    private int bestValue;

    public ZeroAndOnePackage(Knapsack[] knapsacks, int totalWeight) {
        super();
        this.knapsacks = knapsacks;
        this.totalWeight = totalWeight;
        this.num = knapsacks.length;
        /*物品依據單位重量價值進行排序*/
        Arrays.sort(knapsacks, Collections.reverseOrder());
    }

    public int getBestValue() {
        return bestValue;
    }


    /*價值上限=節點現有價值+背包剩余容量*剩余物品的最大單位重量價值
     *當物品由單位重量的價值從大到小排列時，計算出的價值上限大于所有物
     *品的總重量，否則小于物品的總重量當放入背包的物品越來越來越多時，
     *價值上限也越來越接近物品的真實總價值
     */
    private int getPutValue(Node node) {
        /*獲取背包剩余容量*/
        int surplusWeight = totalWeight - node.currWeight;
        int value = https://www.cnblogs.com/blknemo/p/node.currValue;
        int i = node.index;

        while (i < this.num && knapsacks[i].getWeight() <= surplusWeight) {
            surplusWeight -= knapsacks[i].getWeight();
            value += knapsacks[i].getValue();
            i++;
        }
        /*當物品超重無法放入背包中時，可以通過背包剩余容量*下個物品單位重量的價值計算出物品的價值上限*/
        if (i < this.num) {
            value += knapsacks[i].getUnitValue() * surplusWeight;
        }
        return value;
    }
    
    public void findMaxValue() {
        LinkedList nodeList = new LinkedList();

        /*起始節點當前重量和當前價值均為0*/
        nodeList.add(new Node(0, 0, 0));
        while (!nodeList.isEmpty()) {
            /*取出放入佇列中的第一個節點*/
            Node node = nodeList.pop();

            // 如果當前結點的上限大于等于最大價值并且結點索引小于物品總數，那就可以進行操作
            // 否則，沒啥操作的必要，上限都沒當前最大價值大，何必操作呢
            if (node.upperLimit >= bestValue && node.index < num) {
                /*左節點：該節點代表物品放入背包中，上個節點的價值+本次物品的價值為當前價值*/
                int leftWeight = node.currWeight + knapsacks[node.index].getWeight();
                int leftValue = node.currValue + knapsacks[node.index].getValue();
                Node left = new Node(leftWeight, leftValue, node.index + 1);
                /*放入當前物品后可以獲得的價值上限*/
                left.upperLimit = getPutValue(left);
                /*當物品放入背包中左節點的判斷條件為保證不超過背包的總承重*/
                if (left.currWeight <= totalWeight && left.upperLimit > bestValue) {
                    /*將左節點添加到佇列中*/
                    nodeList.add(left);
                    if (left.currValue > bestValue) {
                        /*物品放入背包不超重，且當前價值更大，則當前價值為最大價值*/
                        bestValue = left.currValue;
                    }
                }
                /*右節點：該節點表示物品不放入背包中，上個節點的價值為當前價值*/
                Node right = new Node(node.currWeight, node.currValue,node.index + 1);
                /*不放入當前物品后可以獲得的價值上限*/
                right.upperLimit = getPutValue(right);
                if (right.upperLimit >= bestValue) {
                    /*將右節點添加到佇列中*/
                    nodeList.add(right);
                }
            }
        }
    }

    public static void main(String[] args) {
        Knapsack[] knapsack = new Knapsack[] { 
                new Knapsack(2, 13),new Knapsack(1, 10), new Knapsack(3, 24), new Knapsack(2, 15),
                new Knapsack(4, 28), new Knapsack(5, 33), new Knapsack(3, 20),new Knapsack(1, 8)};
        int totalWeight = 12;
        ZeroAndOnePackage zeroAndOnePackage = new ZeroAndOnePackage(knapsack, totalWeight);

        zeroAndOnePackage.findMaxValue();
        System.out.println("最大價值為："+zeroAndOnePackage.getBestValue());
    }
}

優化理論

1. 問題描述

設有n個物體和一個背包,物體i的重量為wi價值為pi ,背包的載荷為M, 若將物體i（1<= i <=n）裝入背包,則有價值為pi . 目標是找到一個方案, 使得能放入背包的物體總價值最高.

設N=3, W=(16,15,15), P=(45,25,25), C=30（背包容量）

2. 佇列式分支限界法

可以通過畫分支限界法狀態空間樹的搜索圖來理解具體思想和流程

每一層按順序對應一個物品放入背包（1）還是不放入背包（0）

步驟：

用一個佇列存盤活結點表，初始為空
A為當前擴展結點，其兒子結點B和C均為可行結點，將其按從左到右順序加入活結點佇列，并舍棄A，
按FIFO原則，下一擴展結點為B，其兒子結點D不可行，舍棄；E可行，加入，舍棄B
C為當前擴展結點，兒子結點F、G均為可行結點，加入活結點表，舍棄C
擴展結點E的兒子結點J不可行而舍棄；K為可行的葉結點，是問題的一個可行解，價值為45
當前活結點佇列的隊首為F, 兒子結點L、M為可行葉結點，價值為50、25
G為最后一個擴展結點，兒子結點N、O均為可行葉結點，其價值為25和0
活結點佇列為空，演算法結束，其最優值為50

注意：活結點就是不可再進行擴展的節點，也就是兩個兒子還沒有全部生成的節點

3. 優先佇列式分支限界法

3.1 以活結點價值為優先級準則

步驟：

用一個極大堆表示活結點表的優先佇列，其優先級定義為活結點所獲得的價值，初始為空，
由A開始搜索解空間樹，其兒子結點B、C為可行結點，加入堆中，舍棄A，
B獲得價值45，C為0. B為堆中價值最大元素，并成為下一擴展結點，
B的兒子結點D是不可行結點，舍棄，E是可行結點，加入到堆中，舍棄B，
E的價值為45，是堆中最大元素，為當前擴展結點，
E的兒子J是不可行葉結點，舍棄，K是可行葉結點，為問題的一個可行解價值為45，
繼續擴展堆中唯一活結點C，直至存盤活結點的堆為空，演算法結束，
演算法搜索得到最優值為50，最優解為從根結點A到葉結點L的路徑（0，1，1），

3.2 以限界函式為優先級準則

應用貪心法求得近似解為(1, 0, 0, 0)，獲得的價值為40，這可以作為0/1背包問題的下界，

如何求得0/1背包問題的一個合理的上界呢？考慮最好情況，背包中裝入的全部是第1個物品且可以將背包裝滿，則可以得到一個非常簡單的上界的計算方法：

b=W×(v1/w1)=10×10=100，于是，得到了目標函式的界[40, 100]，

所以我們定義限界函式為：
\[ub=v+(W+w)*(v_{i+1}/w_{i+1})\]

再來畫狀態空間樹的搜索圖：

步驟：

在根結點1，沒有將任何物品裝入背包，因此，背包的重量和獲得的價值均為0，根據限界函式計算結點1的目標函式值為10×10=100；
在結點2，將物品1裝入背包，因此，背包的重量為4，獲得的價值為40，目標函式值為40 + (10-4)×6=76，將結點2加入待處理結點表PT中；在結點3，沒有將物品1裝入背包，因此，背包的重量和獲得的價值仍為0，目標函式值為10×6＝60，將結點3加入表PT中；
在表PT中選取目標函式值取得極大的結點2優先進行搜索；
在結點4，將物品2裝入背包，因此，背包的重量為11，不滿足約束條件，將結點4丟棄；在結點5，沒有將物品2裝入背包，因此，背包的重量和獲得的價值與結點2相同，目標函式值為40 + (10-4)×5=70，將結點5加入表PT中；
在表PT中選取目標函式值取得極大的結點5優先進行搜索；
在結點6，將物品3裝入背包，因此，背包的重量為9，獲得的價值為65，目標函式值為65 + (10-9)×4=69，將結點6加入表PT中；在結點7，沒有將物品3裝入背包，因此，背包的重量和獲得的價值與結點5相同，目標函式值為40 + (10-4)×4＝64，將結點6加入表PT中；
在表PT中選取目標函式值取得極大的結點6優先進行搜索；
在結點8，將物品4裝入背包，因此，背包的重量為12，不滿足約束條件，將結點8丟棄；在結點9，沒有將物品4裝入背包，因此，背包的重量和獲得的價值與結點6相同，目標函式值為65；
由于結點9是葉子結點，同時結點9的目標函式值是表PT中的極大值，所以，結點9對應的解即是問題的最優解，搜索結束，

總結：

剪枝函式給出每個可行結點相應的子樹可能獲得的最大價值的上界，
如這個上界不會比當前最優值更大，則可以剪去相應的子樹，
也可將上界函式確定的每個結點的上界值作為優先級，以該優先級的非增序抽取當前擴展結點，由此可快速獲得最優解，

題外話

分支界限法一直是我比較喜歡的演算法思想，我們的人生不就是這樣一棵二叉樹嗎？從出生開始最終走向終點，不同的道路決定不同的終點，在每個分岔口不妨試著用分支界限法的思想幫助我們做出判斷，快速走向最美好的人生，對于每次選擇，我們不妨先算一算它的最優和最差結果，對于最優結果，我們可以想一想它值不值得我們付出精力去做，對于最差結果，我們想一想能不能承擔的了，或許不需要結果，在計算的程序中突然就有了答案，，，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/263251.html

標籤：其他

上一篇：CODEFORCES 704 div2 題解（e待補）

下一篇：docker可視化工具portainer-單機

【演算法】分支界限法

分支界限法

概念

基本思想

適用場景

分支界限三步走

撰寫檢測函式（非必須）

建立狀態結點

明確所有分支

尋找界限條件

實體

01背包問題

優化

上界估算優化

優化理論

1. 問題描述

2. 佇列式分支限界法

3. 優先佇列式分支限界法

3.1 以活結點價值為優先級準則

3.2 以限界函式為優先級準則

題外話