dfs求解01背包與分支限界法求解旅行售貨員問題（java）

1.利用回溯法求解01背包問題。

對于N個物品，在背包的總體積的限制下，有些物品肯定是該舍棄的。

對于每件物品都有取和不取倆種情況。

我們把所有的情況周遊一次，最後取最優的結果。

總體上來就是暴力枚舉求最優解。

為了更快地求出最優解，有些情況枚舉到一半可以立馬舍棄。

如果拿了目前物品，背包總體積大小會溢出，那麼這種情況到這一步就會立馬放棄接下來的枚舉。

代碼

java

public class Main {
    static int N=7;//物品總的個數
    static int maxW=25;//背包容量
    static int maxV=0;//目前已經裝了的最大價值
    static int w[]={0,11,7,9,12,3,10};//體積
    static int v[]= {0,10,5,7,9,2,12};//價值
    static int vis[]=new int[N];//用于标記哪些物品被選了
    public static void main(String[] args) {
        dfs(1,0,0,new int[N]);
        int ans=0;//記錄選擇物品的價值
        System.out.print("選擇的物品是:");
        for(int i=1;i<N;i++){

            if(vis[i]==1) {
                System.out.print(i + "，");
                ans+=v[i];
            }
        }
        System.out.println();
        System.out.println("此時價值最大，即"+ans);

    }
    public static void dfs(int idx,int curV,int curW,int curVis[]){//第idx個物品，已經裝了curV價值，curW重量,curVis用于标記選了哪些物品
        if(idx==N) {//物品搜尋完畢
            if(curV>maxV){
                maxV=curV;//更新已知的可裝價值最大值
                //vis=curVis;
                for(int i=0;i<N;i++){//重新指派記錄選中的物品個數
                    vis[i]=curVis[i];
                }
            }

            return;
        }
        curVis[idx]=0;//目前物品不取
        dfs(idx+1,curV,curW,curVis);
        if(curW+w[idx]<=maxW){//如果目前物品裝得下(剪枝)
            //這個物品裝了
            curVis[idx]=1;//标記裝入
            dfs(idx+1,curV+v[idx],curW+w[idx],curVis);
        }
    }
}

c++

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=7;//物品總的個數

int maxW=25;//背包容量
int maxV=0;//目前已經裝了的最大價值
int w[]={0,11,7,9,12,3,10};//體積
int v[]= {0,10,5,7,9,2,12};//價值
int vis[N];//用于标記哪些物品被選了

void dfs(int idx,int curV,int curW,int curVis[]){//第idx個物品，已經裝了curV價值，curW重量,curVis用于标記選了哪些物品
        if(idx==N) {//物品搜尋完畢
            if(curV>maxV){
                maxV=curV;//更新已知的可裝價值最大值
                //vis=curVis;
                for(int i=0;i<N;i++){//重新指派記錄選中的物品個數
                    vis[i]=curVis[i];
                }
            }

            return;
        }
        curVis[idx]=0;//目前物品不取
        dfs(idx+1,curV,curW,curVis);
        if(curW+w[idx]<=maxW){//如果目前物品裝得下(剪枝)
            //這個物品裝了
            curVis[idx]=1;//标記裝入
            dfs(idx+1,curV+v[idx],curW+w[idx],curVis);
        }
}
    
int main(){
    dfs(1,0,0,new int[N]);
        int ans=0;//記錄選擇物品的價值
        cout<<"選擇的物品是:"<<endl;
        for(int i=1;i<N;i++){

            if(vis[i]==1) {
                cout<<i << "，";
                ans+=v[i];
            }
        }
        cout<<endl;
        cout<<"此時價值最大，即"<<ans<<endl;
}

結果

dfs求解01背包與分支限界法求解旅行售貨員問題（java）

2.利用分支界限法求解旅行售貨員問題（隻有java代碼）

下面代碼采用的是一般的dfs解法（為什麼會列出這個解法呢，因為我了解 分支界限法
之前隻會這個解法，咳咳）

求出的是滿足條件的所有解，然後才選取其中一種（dfs）。

而分支界限法是直接求出一個最優解，下面最後介紹（bfs）。

public class Main {
    static int N=5;//城市個數
    static int g[][]=new int[N][N];
    static int ne[]=new int[N];//用于存目前點的下一個城市編号
    static int vis[]=new int[N];//用于記錄已經走過的城市
    static int minV=Integer.MAX_VALUE;//用于存目前最小的路徑花費
    public static void main(String[] args) {
        g[1][2]=30;g[2][1]=30;
        g[1][4]=4;g[4][1]=4;
        g[1][3]=6;g[3][1]=6;
        g[2][3]=5;g[3][2]=5;
        g[2][4]=10;g[4][2]=10;
        g[3][4]=20;g[4][3]=20;
        dfs(1,1,0,new int[N]);
        System.out.println("最短回路長為："+minV);
        System.out.print("最短回路為：");
        int t=1;//旅遊開始城市
        System.out.print("1 ");
        for(int i=1;i<N-1;i++){
            System.out.print(ne[t]+" ");
            t=ne[t];
        }
    }
    public static void dfs(int idx,int n,int curV,int curN[]){//第idx層,n号城市,目前路徑花費curV,curN目前路徑記錄
        if(idx==N-1){//所有城市走完後，選擇最優解
            if(curV+g[n][1]<minV){
                minV=curV+g[n][1];
                for(int i=1;i<N-1;i++){
                    ne[i]=curN[i];
                }
                ne[n]=1;//最後一個城市就是起點城市1
            }
            return;
        }
        vis[n]=1;//将目前城市标記已經走過
        for(int i=1;i<N;i++){//周遊下一個城市
            if(vis[i]==0&&g[n][i]!=Integer.MAX_VALUE){//如果下一個城市沒有走過并且可以走通
                //剪枝
                if(curV+g[n][i]<minV){//目前的路徑花費小于曆史最優花費才有可能産生最優解
                    //走
                    vis[i]=1;//标記目前城市已經走
                    curN[n]=i;//記錄目前路徑
                    dfs(idx+1,i,curV+g[n][i],curN);
                    vis[i]=0;//還原現場
                }
            }
        }
    }
}

運作結果

dfs求解01背包與分支限界法求解旅行售貨員問題（java）

進入正題，分支界限法，這個聽着很厲害，有利于大量的需要剪枝的場景（剪枝極快）。

算法的核心是建構可行解樹。采用bfs隊列或者優先隊列實作。
但是代碼實作卻有點難度

dfs求解01背包與分支限界法求解旅行售貨員問題（java）

import java.util.Collections;
import java.util.LinkedList;
public class Main{
    static int N=5;
    static int g[][]=new int[N][N];
    public static void main(String[] args){
        g[1][2]=30;g[2][1]=30;
        g[1][4]=4;g[4][1]=4;
        g[1][3]=6;g[3][1]=6;
        g[2][3]=5;g[3][2]=5;
        g[2][4]=10;g[4][2]=10;
        g[3][4]=20;g[4][3]=20;
        int v[]={1,2,3,4,5};
        BBTSP bbtsp = new BBTSP(g);
        int ans = bbtsp.bbTsp(v);
        System.out.println("最短回路長為:"+ans);
        System.out.print("最短回路為:");
        for(int i=1;i<N;i++){
            System.out.print(v[i]+" ");
        }
        
    }
}
class BBTSP {
    int[][] a;//圖G的鄰接矩陣

    public BBTSP(int[][] a) {
        this.a = a;
    }

    public static class HeapNode implements Comparable {
        int lcost;//子樹費用的下界
        int cc;//目前費用
        int rcost;//x[s:n-1]中頂點最小出邊費用和
        int s;//根節點到目前節點的路徑為x[0:s]
        int[] x;//需要進一步搜尋的頂點是x[s+1:n-1]

        //構造方法
        public HeapNode(int lc, int ccc, int rc, int ss, int[] xx) {
            lcost = lc;
            cc = ccc;
            s = ss;
            x = xx;
        }

        public int compareTo(Object x) {
            int xlc = ((HeapNode) x).lcost;
            if (lcost < xlc) return -1;
            if (lcost == xlc) return 0;
            return 1;
        }
    }

    public int bbTsp(int[] v) {//解決旅行售貨員問題的優先隊列分支界限法
        int n = v.length - 1;//節點數
        //MinHeap heap=new MinHeap();
        LinkedList<HeapNode> heap = new LinkedList<HeapNode>();
        //minOut[i]=i的最小出邊費用
        int[] minOut = new int[n + 1];
        int minSum = 0;//最小出邊費用和
        for (int i = 1; i <= n; i++) {//針對每個節點，找到最小出邊
            //計算minOut[i]和minSum
            int min = Integer.MAX_VALUE;
            for (int j = 1; j <= n; j++)
                if (a[i][j] < Integer.MAX_VALUE && a[i][j] < min)
                    min = a[i][j];

            if (min == Integer.MAX_VALUE)
                return Integer.MAX_VALUE;//沒有回路
            minOut[i] = min;
            minSum += min;
        }

        //初始化
        int[] x = new int[n];
        for (int i = 0; i < n; i++)
            x[i] = i + 1;
        HeapNode enode = new HeapNode(0, 0, minSum, 0, x);
        Integer bestc = Integer.MAX_VALUE;

        //搜尋排列空間樹
        while (enode != null && enode.s < n - 1) {
            //非葉節點
            x = enode.x;
            if (enode.s == n - 2) {
                //目前擴充結點是葉節點的父節點
                //再加兩條邊構成回路
                //所構成回路是否優于目前最優解
                if (a[x[n - 2]][x[n - 1]] != -1 && a[x[n - 1]][1] != -1 && enode.cc + a[x[n - 2]][x[n - 1]] + a[x[n - 1]][1] < bestc) {
                    //找到費用更小的回路
                    bestc = enode.cc + a[x[n - 2]][x[n - 1]] + a[x[n - 1]][1];
                    enode.cc = bestc;
                    enode.lcost = bestc;
                    enode.s++;
                    heap.add(enode);
                    Collections.sort(heap);
                }
            } else {//内部結點
                //産生目前擴充結點的兒子結點
                for (int i = enode.s + 1; i < n; i++) {
                    if (a[x[enode.s]][x[i]] != -1) {
                        //可行兒子結點
                        int cc = enode.cc + a[x[enode.s]][x[i]];
                        int rcost = enode.rcost = minOut[x[enode.s]];
                        int b = cc + rcost;//下界
                        if (b < bestc) {
                            //子樹可能含有最優解，結點插入最小堆
                            int[] xx = new int[n];
                            for (int j = 0; j < n; j++)
                                xx[j] = x[j];
                            xx[enode.s + 1] = x[i];
                            xx[i] = x[enode.s + 1];
                            HeapNode node = new HeapNode(b, cc, rcost, enode.s + 1, xx);
                            heap.add(node);
                            Collections.sort(heap);
                        }
                    }
                }

            }

            //取下一個擴充結點
            enode = heap.poll();
        }
        //将最優解複制到v[1...n]
        for (int i = 0; i < n; i++)
            v[i + 1] = enode.x[i];
        return bestc;
    }
}

運作結果

dfs求解01背包與分支限界法求解旅行售貨員問題（java）

總結：承認别人比自己優秀，自己是個普普通通的凡人不難。第二個分支界限法核心代碼是摘自網絡上别人寫的。

我經過一個小時成功大緻搞懂了分支界限法的理論，隻是理論！！而代碼現在卻無法成功實作。

另外，有個運作時間，可以看到同樣的資料内容，分支界限法用了
83ms ,而我自己寫的dfs隻用了 76ms (咳咳，給自己個台階下~)

dfs求解01背包與分支限界法求解旅行售貨員問題（java）

1.利用回溯法求解01背包問題。

代碼

2.利用分支界限法求解旅行售貨員問題（隻有java代碼）

繼續閱讀

POJ_1985_Cow Marathon(樹的直徑)

CF1394C 計算幾何

leetcode_17.Letter Combinations of a Phone Number

HDU 1286 找新朋友（歐拉函數模闆）

hdu 1286 找新朋友（歐拉函數）

哈理工oj Touring （最短路 dij算法鄰接表 + 隊列）

HDU 1286 找新朋友(歐拉函數)找新朋友

HDU 5119 Happy Matt Friends（dp） Happy Matt Friends

CF-346 D. Robot Control(反向建圖spfa)

ACMer成長之路

pat（B）1009. 說反話（逆疊代器）

關于多項式的一點研究及其在ACM競賽中的應用關于多項式的一點研究及其在ACM競賽中的應用

codeforces 838D D. Airplane Arrangements 構造法推公式

HDU Reorder the Books

POJ 1284 Primitive Roots (歐拉函數&原根定理)

hdu 4741 Save Labman No.004（計算幾何） Save Labman No.004