【題意】
給定一個n個頂點組成的帶權的有向圖的距離矩陣d[i,j],要求從0開始結果所有點一次回到0,問所經過邊的總權重的最小值為多少
【思路】
旅行商問題TSP,狀态壓縮dp,記憶化dp
【分析】
假設目前已經通路過的頂點集合為S,(起點0當作還未通路過的點),目前所在的頂點為v,用dp[S][v]表示從v出發通路剩餘所有的點最終回到0的最小權重和。
dp[V][0]=0;
dp[S][u]=min(dp[S|{v}[v]]+a[u][v]) ( v不屬于S )
【代碼】
#include<bits/stdc++.h>
using namespace std;
const int maxn = 11;
const int inf = 0x3f3f3f3f;
int a[maxn][maxn];
int dp[1 << maxn][maxn];//dp[i][j]表示已經經過的節點集合為i,目前位于j,從j出發通路剩餘節點回到0的最小距離
int n;
int dfs(int S, int u) {
if (dp[S][u] != -1)return dp[S][u];
if (S == (1 << (n+1)) - 1 && u == 0) return dp[S][u] = 0;
int res = inf;
for (int v = 0; v <= n; v++) {
if (!(S >>v & 1)) {
res = min(res, dfs(S | (1 << v), v)+a[u][v]);
}
}
return dp[S][u] = res;
}
int main() {
while (~scanf("%d", &n),n) {
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
scanf("%d", &a[i][j]);
}
}
for (int k = 0; k <= n; k++) {
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
}
}
}
memset(dp, -1, sizeof(dp));
printf("%d\n", dfs(0, 0));
}
}
循環代碼
int dp[1 << maxn][maxn];//dp[i][j]表示已經經過的節點集合為i,目前位于j,從j出發通路剩餘節點回到0的最小距離
int n;
//轉移:dp[S][v]=min(dp[S][v],dp[S|1<<u][u]+d[v][u]);
void solve() {
memset(dp, inf, sizeof(dp));
dp[(1 << n ) - 1][0] = 0;
for (int S = (1 << n) - 2; S >= 0; S--) {
for (int v = 0; v <= n; v++) {
for (int u = 0; u <= n; u++) {
if(!(S>>u&1))
dp[S][v] = min(dp[S][v], dp[S | (1 << u)][u] + a[v][u]);
}
}
}
printf("%d\n", dp[0][0]);
}