城市个数n(1<n≤20,包括北京)
城市间的车票价钱 n行n列的矩阵 m[n][n]
最小车费花销 s
4 0 2 6 5 2 0 4 4 6 4 0 2 5 4 2 0
13
共 4 个城市,城市 1 和城市 1 的车费为0,城市 1 和城市 2 之间的车费为 2,城市 1 和城市 3 之间的车费为 6,城市 1 和城市 4 之间的车费为 5,依次类推。假设任意两个城市之间均有单程票可购买,且票价在1000元以内,无需考虑极端情况。
#include <bits/stdc++.h> using namespace std; int main() { uint n; cin >> n; assert(n > 1); uint m[n][n]; for (uint i = 0; i < n; ++i) for (uint j = 0; j < n; ++j) cin >> m[i][j]; --n; //因为以后只用到n-1了,所以直接自减1 uint dp[1 << n][n]; //[访问过的城市标记][当前城市] memset(dp, 0x7f, sizeof(dp)); //0x7f防止unsigned溢出 //默认从第n-1个城市开始走出第一步 for (uint i = 0; i < n; ++i) dp[1 << i][i] = m[n][i]; uint s = 1; for (; s < (1 << n) - 1; ++s) for (uint i = 0; i < n; ++i) for (uint j = 0; j < n; ++j) { uint t = s | (1 << j); if (t != s) dp[t][j] = min(dp[t][j], dp[s][i] + m[i][j]); } uint a = UINT_MAX; for (uint i = 0; i < n; ++i) a = min(a, dp[s][i] + m[i][n]); cout << a; }
import java.util.*; public class Main { //备忘录 public static int[][] memo; //自上而下的dp函数 public static int dp(int city, int j, int[][] dist) { //中止条件 if(j == 0) return dist[city][0]; //如果命中,直接返回 if(memo[city][j] != -1) return memo[city][j]; int ans = Integer.MAX_VALUE; for(int i = 1; i < dist.length; i++) { if(((j >> (i-1)) & 1) == 1) { j ^= (1 << (i-1)); //记录这一轮的最小答案 ans = Math.min(ans, dist[city][i]+dp(i, j, dist)); j ^= (1 << (i-1)); } } //添加至备忘录 memo[city][j] = ans; return ans; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int cityNum = in.nextInt();// 城市数目 int[][] dist = new int[cityNum][cityNum]; for (int i = 0; i < dist.length; i++) { for (int j = 0; j < cityNum; j++) { dist[i][j] = in.nextInt(); } } //对1进行左移n-1位,值刚好等于2^(n-1) int V = 1 << (cityNum - 1); memo = new int[cityNum][V]; //初始化memo备忘录 for (int i = 0; i < cityNum; i++) { for(int j = 0; j < V; j++) { memo[i][j] = -1; } } int ans = dp(0 , V-1, dist); System.out.println(ans); } }
动态规划解决问题:
通过率50% ,其余超时
题目难点在于状态定义,关键点:题目理解。题目中要求回到北京,是一个定义状态麻烦的点。
状态定义: 代表由 i 城市出发,经过 nodes 里面所有节点,回到北京的最低费用。
状态转移方程:
,
边界方程: 当 ,花销直接可以定下来 ,
算法流程:
1. 根据输入构建花销矩阵,
2. 构建除北京外的节点列表
3. 返回 结果即可
n = int(input()) cost = [] for i in range(n): cost.append(list(map(int , input().split()))) def dp( i , nodes): if len(nodes)== 1: return cost[i][nodes[0]] + cost[nodes[0]][0] res = [float("inf") for _ in range(len(nodes))] for index ,node in enumerate(nodes): res[index] = cost[i][node] + dp(node , nodes[:index] + nodes[index+1:]) return min(res) nodes = [i for i in range(1,n)] print(dp(0, nodes))
# 运行时,内存超了,贴出来想一起讨论讨论(虽然写得不咋地) import itertools n = int(input()) L = [] for i in range(n): L.append(list(map(int, input().split(' ')))) def treaval(L, n): # 除起点之外的不同路线组合 com = list(itertools.permutations(list(range(1, n)), n - 1)) # print(com) spend = 9999 # 假设一开始花销很大 for j in range(len(com)): # 获取其中一种组合之后就释放 road = list(com.pop(0)) # 补全起点 for i in range(n): if i not in road: road.append(i) road.insert(0, i) x = 0 # 当前路线的花销 for i in range(n): x = x + L[road[i]][road[i + 1]] # 最小花销 if x < spend: spend = x return spend print(treaval(L, n))
#include <bits/stdc++.h> using namespace std; #define INF 0x7fffffff int getAns(vector<vector<int>> &Path) {// Path 为一个常量矩阵的引用 int M = INF; // 定义一个极大值,如果新的状态包含走过的点,则将其设置为极大 int N = Path.size(); // 获取给定数组的长度,这里为城市节点数 vector<vector<int>> dp(1<<N,vector<int> (N,M)); //初始化vector对象,包含2^N个元素,每个元素的值为vector<int> (N,M) dp[1][0] = 0; // 假设固定出发点为0,从0出发回到0的花费为0。 // dp[经过城市的结合,为二进制压缩状态][当前进过的城市id] for(int i=1;i<N;i++) dp[1<<i][i] = M; // 如果当前城市已在走过的路径集合中,则跳过 // 因为我们要的是小值,所以将此值设置的很大, for(int i=1;i<(1<<N);i++) // 遍历所有的状态 { for(int j=0;j<N;j++) // 遍历城市节点,出发点 { if(dp[i][j] != M) {// 如果当前城市没有在走过的集合中 for(int k=0;k<N;k++) {// 遍历城市节点,经过点 if((i&(1<<k)) == 0) // 如果当前城市没有在走过的集合中 dp[i|(1<<k)][k] = min(dp[i|(1<<k)][k],dp[i][j] + Path[j][k]); // 当前路径的代价加入到集合中,并取最小的值 } } } } int ans = M; // 要取最小,所以先给个最大; for(int i=0;i<N;i++) // 因为固定了出发点,所以要加上到城市0的距离。另外要从所有的完成整个环路的集合V’中选择,完成最后的转移 /*********************************************************** * 0<----->1 也就是从任意一点出发走完所有的点 * * | | 都需要在加上从该点到出发点的距离 * * | X | 这样才能形成一个完整的环 * * | | 此时dp[][i]表示从i点走完所有点的最小值 * * 2<----->3 * ************************************************************/ ans = min(ans,dp[(1<<N)-1][i] + Path[i][0]); return ans; }// getAns int main(){ int n; while(cin>>n){ //输入矩阵大小 vector<vector<int>> edges(n,vector<int>(n,0)); //初始化矩阵; for(int i=0; i<n; i++){ // 循环输入各节点的值 for(int j=0; j<n; j++){ cin>>edges[i][j]; } } cout<<getAns(edges)<<endl; // 函数调用 } return 0; }
不会,参考了前面的答案,为其添加了注释
#include <iostream> #include <vector> #include <algorithm> using namespace std; int getAns(vector<vector<int>> &nums){ const int MAX = 0x0fffffff; int n = nums.size(); int stateNum = 1 << n; // dp[i][j]中的i是一个二进制形式的数,表示经过城市的集合,如0111表示经过了城市0,1,2 // dp[i][j]表示经过了i中的城市,并且以j结尾的路径长度 vector<vector<int> > dp(stateNum,vector<int>(n,MAX)); dp[1][0] = 0; //从城市0出发,所以经过城市0,以城市0结尾的路径为0 //从城市0出发,更新和其他城市的距离 for(int i=1;i<stateNum;i++){ for(int j=0;j<n;j++){ if(dp[i][j] != MAX){ //如果已经访问过 for(int k=0;k<n;k++){ if( (i & (1 << k) ) == 0){ //没有访问过k,且从这里到k的距离小于原来的距离,则更新 dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k],dp[i][j] + nums[j][k]); } } } } } int res = MAX; for(int i=1;i<n;i++){ res = min(res,dp[stateNum-1][i] + nums[i][0]); } return res; } int main(int argc, char const *argv[]) { int n; while(cin>>n){ vector<vector<int>> edges(n,vector<int>(n,0)); int x; for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ cin>>edges[i][j]; } } cout<<getAns(edges)<<endl; } return 0; }
#include<stdio.h> #include<iostream> #include<vector> #include<cmath> #include<cstring> using namespace std; int main(){ int n; int dis[22][22]; scanf("%d",&n); int jh = pow(2,n-1)-1; vector<vector<int>> dp; for(int i=0;i<n;i++){ dp.push_back(vector<int>()); for(int j=0;j<=jh;j++){ dp[i].push_back(99999); } } for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&dis[i][j]); for(int i=1;i<n;i++){ dp[i][0] = dis[i][0]; } for(int i=1;i<=jh;i++){ for(int j=0;j<n;j++){ if(j!=0 && i>>(j-1) & 1 == 1) continue; else{ for(int k = 1;k<n;k++){ if(i>>(k-1) & 1 == 0) continue; else{ if(dp[j][i]>(dp[k][i ^ (1<<(k-1))] + dis[j][k])) dp[j][i] = dp[k][i ^ (1<<(k-1))] + dis[j][k]; } } } } } printf("%d",dp[0][jh]); return 0; }
添加一个简单的Python版本吧。
思路和上面的大佬一样,但不知道为什么用Python会超时。
#TSP 状压DP n = int(input()) m = [] for i in range(n): m.append(list(map(int, input().split()))) V = 1 << (n-1) #从左至右每一位二进制代表第i个城市是否被访问 如1000代表,第一个城市被访问,而其他城市没有 dp = [[float("inf")] * V for i in range(n)] # dp[i][j]:从节点i只经过集合j所有点再回到0点所需要的最小开销 for i in range(n): dp[i][0] = m[i][0] for j in range(1,V): for i in range(n): for k in range(1,n): #能不能先到k城市 if (j >> (k-1) & 1) == 1: #可以途径k dp[i][j] = min(dp[i][j], m[i][k] + dp[k][j ^ (1 << (k-1))]) #从0出发,经过所有点,再回到0的费用 print(dp[0][(1 << (n-1)) - 1])
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[][] nums = new int[N][N]; for(int i=0; i < N; i++){ for(int j=0; j < N; j++){ nums[i][j] = sc.nextInt(); } } Integer[][] memo = new Integer[(1<<N)][N]; System.out.println(DFS(nums, 0, 0, memo)); } private static int DFS(int[][] nums, int idx, int state, Integer[][] memo){ int n = nums.length; if(state == (1<<n)-2){ //防止出现0-1-2-0-3的情况 return nums[idx][0]; } if(memo[state][idx] != null) return memo[state][idx]; int ret = Integer.MAX_VALUE; for(int i=1; i < n; i++){ if((state & (1<<i)) != 0) continue; ret = Math.min(ret, nums[i][idx] + DFS(nums, i, (state ^ (1<<i)), memo)); } memo[state][idx] = ret; return ret; } }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[][] dist = new int[n][n]; for (int i = 0; i < dist.length; i++) { for (int j = 0; j < n; j++) { dist[i][j] = in.nextInt(); } } in.close(); //随便挑一个作为起点,为方便计算,就选择0城市就好, // 那么对应的事件可以理解为从0号城市出发去(1号、2号、3号城市)最后回到0号城市,其中中间的1、2、3之间的顺序不清楚怎么去的。 //但是可以发现事件最小消耗为min(从0->1的距离+从1号到{2号、3号}最后回到0的距离、 // 从0->2的距离+从2号到{1号、3号}最后回到0的距离、 // 从0->3的距离+从1号到{1号、2号}最后回到0的距离)。 // 用bit第几位是否为1表示当前事件有哪几号城市。{2号、3号}——> 110; int V = 1 << (n - 1); int[][] dp = new int[n][V]; dp[0][0] = 0; for (int j = 0; j < V; j++) { for (int i = 0; i < n; i++) { if (j == 0) { //表示从第i个城市到第j(0)个城市的最小路径。正好就是第i个城市去第0个城市的距离。 dp[i][j] = dist[i][j] + dp[0][0]; } else { dp[i][j] = Integer.MAX_VALUE; for (int k = 1; k < n; k++) { //表示第k位城市。 int index = (1 << (k - 1)); //当前的dp应该是遍历了j城市集的每一个城市对应的子dp+i到k的距离,求得的其中的最小的那个值; if ((index & j) > 0) { //找到其中的一个k; //表示j城市集内除了第k位其他的别的城市 int other = j ^ index; dp[i][j] = Math.min(dist[i][k] + dp[k][other], dp[i][j]); } } } } } System.out.println(dp[0][V - 1]); } }
#include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; int V = 1<<(n-1); int a[n][n], dp[n][V]; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>a[i][j]; for(int i=0;i<n;i++) dp[i][0] = a[i][0]; for(int j=1;j<V;j++) for(int i=0;i<n;i++){ dp[i][j] = INT_MAX; if(((j>>(i-1))&1)==0) for(int k=1;k<n;k++) if(((j>>(k-1))&1)==1) dp[i][j] = min(dp[i][j], dp[k][j^(1<<(k-1))]+a[i][k]); } cout<<dp[0][V-1]<<endl; return 0; }
方法二 动态规划 全部通过 #include<iostream> #include<vector> #include<unordered_map> using namespace std; int getAns(vector<vector<int>> &nums){ int M = 0x7ffffff; int n = nums.size(); vector<vector<int>> dp(1<<n, vector<int>(n,M)); dp[1][0] = 0; for(int i=1; i<n; i++) dp[1<<i][i] = M; for(int i=1; i<(1<<n); i++){ for(int j=0; j<n; j++){ if(dp[i][j]!=M){ for(int k=0; k<n; k++){ if((i&(1<<k))==0){ dp[i|(1<<k)][k] = min(dp[i|(1<<k)][k], dp[i][j]+nums[j][k]); } } } } } int ans = M; for(int i=1; i<n; i++){ ans = min(ans, dp[(1<<n)-1][i]+nums[i][0]); } return ans; } int main(){ int n; while(cin>>n){ vector<vector<int>> edges(n,vector<int>(n,0)); int x; for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ cin>>edges[i][j]; } } cout<<getAns(edges)<<endl; } return 0; } 方法一 记忆化搜索只通过了50%
#include<iostream> #include<vector> #include<unordered_map> using namespace std; struct MyHash{ size_t operator()(const pair<int,int> &x) const{ return hash<int>()(x.first) && hash<int>()(x.second); } }; int dp(vector<vector<int>> &nums, unordered_map<pair<int,int>, int, MyHash> &memo, pair<int,int> x, int M){ if(memo.find(x)!=memo.end()) return memo[x]; int ans = M; int n = nums.size(); int last_state = x.first&(~(1<<x.second)); for(int i=0; i<n; i++){ if((last_state&(1<<i))==0) continue; ans = min(ans, nums[i][x.second]+dp(nums, memo, make_pair(last_state,i),M)); } memo[x] = ans; return ans; } int getAns(vector<vector<int>> &nums){ unordered_map<pair<int,int>,int, MyHash> memo; int n = nums.size(); const int M = 0x7fffff; // 假设起点为0号节点 memo[make_pair(1,0)] = 0; for(int i=1; i<n; i++){ memo[make_pair(1<<i,i)] = M; //其它起点为非法状态 } int ans = M; int tmp = (1<<n)-1; for(int i=1; i<n; i++){ ans = min(ans, dp(nums, memo, make_pair(tmp, i), M)+nums[i][0]); } return ans; } int main(){ int n; while(cin>>n){ vector<vector<int>> edges(n,vector<int>(n,0)); int x; for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ cin>>edges[i][j]; } } cout<<getAns(edges)<<endl; } return 0; }
设dp[i][c]为从i出发,经过城市集合c,回到初始城市(这里是城市0)的最小路径。
from functools import cache from math import inf def minCost(n: int, dis: list): u = (1 << n) - 1 - 1 @cache def dfs(i: int, c: int): if c == 0: return dis[0][i] ans = inf for j in range(n): if (c >> j) & 1: ans = min(ans, dis[i][j] + dfs(j, c ^ (1 << j))) return ans return dfs(0, u)
翻译成c++就可以过了!
int minCost(int n, vector<vector<int>> &dis) { int u = (1 << n) - 1 - 1; vector<vector<int>> memo(n, vector<int>(1 << n, -1)); std::function<int(int, int)> dfs = [&](int i, int c) -> int { if (c == 0) return dis[0][i]; if (memo[i][c] != -1) return memo[i][c]; int ans = INT_MAX; for (int j = 0; j < n; j++) if ((c >> j) & 1) ans = min(ans, dis[i][j] + dfs(j, c ^ (1 << j))); memo[i][c] = ans; return ans; }; return dfs(0, u); }151ms
/* 毕业旅行问题 - 题目来源:字节跳动春招研发部分编程题汇总 题目描述: 给定 N(N <= 20) 个城市之间的距离(N行N列的矩阵,对角线元素为0,表示同一个城市到自己的距离为0,其余元素表示两个城市之间的距离), 小明需要从其中的第一个城市出发,到最后一个城市结束,期间需要经过所有其他城市,且每个城市只能经过一次,求最短的路径长度。 解题思路: - 动态规划求解。使用状态压缩的动态规划方法。 - dp[i][j] 表示已经访问过的城市集合为 i,当前在城市 j 的最小路径长度。 - 状态转移方程为 dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + Path[k][j]),其中 k 为上一个访问的城市。 */ /* 动态规划状态转移这段代码是动态规划中的状态转移过程。让我解释一下: 外层循环 for (int i = 1; i < (1 << N); i++) 遍历了所有可能的状态,其中 (1 << N) 表示了城市的总数,即状态的上限。状态 i 表示已经访问过的城市集合,因为有 N 个城市,所以总共有 1 << N 种可能的状态,即 2^N 种。 内层循环 for (int j = 0; j < N; j++) 遍历了当前状态下所有的城市。 条件判断 if (dp[i][j] != M) 检查当前状态是否可达。如果 dp[i][j] 不等于初始值 M,说明状态 i 可以从城市 j 转移而来,即城市 j 已经被访问过。 在内部循环 for (int k = 0; k < N; k++) 中,再次遍历所有城市,寻找下一个可能的城市。 条件判断 if ((i & (1 << k)) == 0) 检查城市 k 是否已经被访问过。如果 (i & (1 << k)) == 0,表示状态 i 中的城市集合还未包含城市 k,可以尝试将城市 k 加入到状态 i 中。 更新状态转移表 dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k], dp[i][j] + Path[j][k])。这里使用位运算将城市 k 加入到状态 i 中,然后更新从城市 j 到城市 k 的最小路径长度,这个长度是通过比较当前状态 i 经过城市 j 到达城市 k 和当前记录的最小值来确定的。 总的来说,这段代码的目的是在已经访问过一部分城市的情况下,尝试将下一个未访问的城市加入到当前状态中,并更新最短路径长度。 */ /* 获取最终答案这段代码用于寻找最终的最短路径长度。 int ans = M; 初始化最终的最短路径长度为一个很大的值 M,初始值设为一个足够大的值是为了确保最终的答案不会超过这个值。 for (int i = 0; i < N; i++) { 遍历所有可能的结束城市,即遍历最后一次访问的城市,因为小明需要从第一个城市出发,到达最后一个城市结束。 ans = min(ans, dp[(1 << N) - 1][i] + Path[i][0]); 在遍历过程中,更新最短路径长度。dp[(1 << N) - 1][i] 表示已经访问过所有城市的状态下,以城市 i 结束的路径长度。Path[i][0] 表示从城市 i 到达终点城市的距离。通过这两个值的相加,得到以城市 i 结束的完整路径长度,并与当前记录的最短路径长度 ans 比较,保留较小的值作为最终答案。 总的来说,这段代码的目的是从所有可能的结束城市中选择一个最小的路径长度作为最终的答案。 */ #include <stdio.h> #include <stdlib.h> #define INF 0x7fffffff // 定义取最小值函数 int min(int a, int b) { return a < b ? a : b; } // 求解最短路径长度函数 int getAns(int** Path, int N) { int M = INF; // 动态分配二维数组 dp,表示状态转移表 int** dp = (int**)malloc((1 << N) * sizeof(int*)); for (int i = 0; i < (1 << N); i++) { dp[i] = (int*)malloc(N * sizeof(int)); // 初始化 dp 数组 for (int j = 0; j < N; j++) { dp[i][j] = M; } } // 初始化起始状态 dp[1][0] = 0; for (int i = 1; i < N; i++) { dp[1 << i][i] = M; } // 动态规划状态转移 for (int i = 1; i < (1 << N); i++) { for (int j = 0; j < N; j++) { if (dp[i][j] != M) { for (int k = 0; k < N; k++) { if ((i & (1 << k)) == 0) { dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k], dp[i][j] + Path[j][k]); } } } } } // 获取最终答案 int ans = M; for (int i = 0; i < N; i++) { ans = min(ans, dp[(1 << N) - 1][i] + Path[i][0]); } // 释放动态分配的内存 for (int i = 0; i < (1 << N); i++) { free(dp[i]); } free(dp); return ans; } int main() { int n; scanf("%d", &n); // 输入城市数量 // 动态分配二维数组 edges,表示城市之间的距离 int** edges = (int**)malloc(n * sizeof(int*)); for (int i = 0; i < n; i++) { edges[i] = (int*)malloc(n * sizeof(int)); // 输入城市之间的距离 for (int j = 0; j < n; j++) { scanf("%d", &edges[i][j]); } } // 计算最短路径长度并输出结果 printf("%d\n", getAns(edges, n)); // 释放动态分配的内存 for (int i = 0; i < n; i++) { free(edges[i]); } free(edges); return 0; }