描述
給定一張 n 個點的帶權(quán)無向圖，點從 0~n-1 標(biāo)號，求起點 0 到終點 n-1 的最短Hamilton路徑。 Hamilton路徑的定義是從 0 到 n-1 不重不漏地經(jīng)過每個點恰好一次。
輸入格式
第一行輸入整數(shù)n。

接下來n行每行n個整數(shù)，其中第i行第j個整數(shù)表示點i到j(luò)的距離（記為a[i,j]）。

對于任意的x,y,z，數(shù)據(jù)保證 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。

輸出格式
輸出一個整數(shù)，表示最短Hamilton路徑的長度。

數(shù)據(jù)范圍
1≤n≤20
0≤a[i,j]≤107
輸入樣例：
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0
輸出樣例：
18

---

---

一看到這道題目的時后我們一眼就覺得這是一道搜索題，但是我們仔細(xì)分析一下時間復(fù)雜度：
頭尾都是確定的，因此我們要對中間的（n - 2）個數(shù)進行全排列，大概就是（n - 2）！次方次排列，于是我們自然而然的就想到了用DP來絕決這個問題，但是用DP我們又該怎么樣來表示這之間的狀態(tài)呢。
每一個位置我們用0，1，來表示。0代表沒走過，1代表已近走過，
由此我們就有了狀態(tài)轉(zhuǎn)移方程。
DP[A][j] = min(DP[A][j], DP[B][k] + value[k][j])
其中A、B，分別時兩個集合。B集合加上點 j 等于A集合。
每個狀態(tài)用其第幾位的二進制是0或者1來表示
我們有了下面的代碼

#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int maxn = (1 << 20) + 10; int dp[maxn][22], value[22][22], n; int main() {cin >> n;for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)cin >> value[i][j];memset(dp, 0x3f, sizeof dp);dp[1][0] = 0;for(int i = 0; i < 1 << n; i++)for(int j = 0; j < n; j++)if(i >> j & 1)for(int k = 0; k < n; k++)if(i - (1 << j) >> k & 1)dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + value[k][j]);cout << dp[(1 << n) - 1][n - 1] << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的二进制状态压缩DP的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。