毕业旅行问题

旅行问题"/>

毕业旅行问题

这个编程题是来自于牛客网的字节跳动2019春招研发部分编程题汇总，有感兴趣的朋友们可以去原网站查看。

小明目前在做一份毕业旅行的规划。打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去一次。由于经费有限，希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销。

输入描述

城市个数n（1<n≤20，包括北京）

城市间的车票价钱 n行n列的矩阵 m[n][n]

输出描述

最小车费花销 s

示例1

输入
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元以内，无需考虑极端情况。

解析

状态压缩动态规划

状态压缩

从状态压缩的特点来看，这个算法适用的题目符合以下的条件：

1. 解法需要保存一定的状态数据（表示一种状态的一个数据值），每个状态数据通常情况下是可以通过 2 进制来表示的。这就要求状态数据的每个单元只有两种状态，比如说棋盘上的格子，放棋子或者不放，或者是硬币的正反两面。这样用 0 或者 1 来表示状态数据的每个单元，而整个状态数据就是一个一串 0 和 1 组成的二进制数。
2. 解法需要将状态数据实现为一个基本数据类型，比如 int，long 等等，即所谓的状态压缩。状态压缩的目的一方面是缩小了数据存储的空间，另一方面是在状态对比和状态整体处理时能够提高效率。这样就要求状态数据中的单元个数不能太大，比如用 int 来表示一个状态的时候，状态的单元个数不能超过 32（32 位的机器）。

位操作实现技巧

• 如果要获得第 i 位的数据，判断((data&(1<<i)) == 0)，若真，为 0，假，为 1；
• 如果要设置第 i 位为 1，data = (data|(1<<i))；
• 如果要设置第 i 位为 0，data = (data&(~(1<<i)))；
• 如果要将第 i 位取反，data = (data^(1<<i)；
• 如果要取出一个数的最后一个 1 (lowbit)：(data&(-data))；

动态规划

略

C++源码

#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，且从j这里到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));for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){cin >> edges[i][j];}}cout << getAns(edges) << endl;}return 0;
}