首页 > 试题广场 > 毕业旅行问题
[编程题]毕业旅行问题
  • 热度指数:2833 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
小明目前在做一份毕业旅行的规划。打算从北京出发,分别去若干个城市,然后再回到北京,每个城市之间均乘坐高铁,且每个城市只去一次。由于经费有限,希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱,找到每个城市只访问一次并返回起点的最小车费花销。

输入描述:
城市个数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元以内,无需考虑极端情况。
import java.util.Scanner;

/**
 * @作者:田九
 * @创建时间:2019年8月12日
 * @项目名称:algorithm.tsp_旅行商问题
 * @类名称:TSP2
 * @类描述:用动态规划的方法解决tsp问题

 */

/**动态规划模型构造
 * 对于4个城市的情况
城市的邻接表如下:
          S0  S1  S2  S3  
   S0   0   3    6     7
   S1   5   0    2     7   
   S2   6   6   0     2
   S3   3   3    5     0
假设找出的一条最短的回路:S0S1S2 S3S0
我们可以利用结论: "S1 S2 S3 S0 "必然是从S1到S0通过其它各点的一条最短路径(如果不是,则会出现矛盾)
Length(总回路) = Length(S0,S1)  + Length(S1,S2,S3,S0)

从上面的公式把总回路长度分解:
Length(回路) =Min{ Length(0,1)+Length(1,…,0), Length(0,2)+Length(2,…,0),Length(0,3)+Length(3,…,0)}
规范化地表达上面的公式
d(i,V) 表示从i点经过点集V各点一次之后回到出发点的最短距离
d(i,V') = min {Cik+d(k,V-{k})}   (k∈V') 
d(k,{ }) = Cik (k≠i)                          
其中,Cik表示i到k的距离     
从城市0出发,经城市1、2、3然后回到城市0的最短路径长度是:
d(0, {1, 2, 3})=min{C01+ d(1, { 2, 3}), C02+ d(2, {1, 3}),C03+ d(3, {1, 2})}

这是最后一个阶段的决策,它必须依据d(1, { 2, 3})、
d(2, {1, 3})和d(3, {1, 2})的计算结果,而: 

d(1, {2, 3})=min{C12+d(2, {3}),  C13+ d(3, {2})}
d(2, {1, 3})=min{C21+d(1, {3}),  C23+ d(3, {1})}
d(3, {1, 2})=min{C31+d(1, {2}),  C32+ d(2, {1})}
继续写下去:
d(1, {2})= C12+d(2, {})   d(2, {3})=C23+d(3, {})   d(3, {2})= C32+d(2, {})  
d(1, {3})= C13+d(3, {})   d(2, {1})=C21+d(1, {})   d(3, {1})= C31+d(1, {})

建立dp表

       
                            
*/
//对之前大佬代码的解读
//注意:经过的路线是一条经过所有城市的闭合回路, 因此从哪一点出发是无所谓的, 因此不妨设从城市0出发。
public class TSP2 {
    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();
            }
        in.close();

        int V = 1 << (cityNum - 1);// 对1进行左移n-1位,值刚好等于2^(n-1)
        // dp表,n行,2^(n-1)列
        int[][] dp = new int[cityNum][V];
        // 初始化dp表第一列
        for (int i = 0; i < cityNum; i++)  dp[i][0] = dist[i][0];
        
        //设想一个数组城市子集V[j],长度为V,且V[j] = j,对于V[j]即为压缩状态的城市集合
        //从1到V-1  用二进制表示的话,刚好可以映射成除了0号城市外的剩余n-1个城市在不在子集V[j],1代表在,0代表不在
        //若有总共有4个城市的话,除了第0号城市,对于1-3号城市
        //111 = V-1 = 2^3 - 1  = 7 ,从高位到低位表示3到1号城市都在子集中
        //而101 = 5 ,表示3,1号城市在子集中,而其他城市不在子集中
        //这里j不仅是dp表的列坐标值,如上描述,j的二进制表示城市相应城市是否在子集中
        for (int j = 1; j < V; j++)   
            for (int i = 0; i < cityNum; i++) { //这个i不仅代表城市号,还代表第i次迭代
                dp[i][j] = Integer.MAX_VALUE; //为了方便求最小值,先将其设为最大值
                if (((j >> (i - 1)) & 1) == 0) { 
                    // 因为j就代表城市子集V[j],((j >> (i - 1))是把第i号城市取出来
                    //并位与上1,等于0,说明是从i号城市出发,经过城市子集V[j],回到起点0号城市
                    for (int k = 1; k < cityNum; k++) { // 这里要求经过子集V[j]里的城市回到0号城市的最小距离
                        if (((j >> (k - 1)) & 1) == 1) { //遍历城市子集V[j]
                            //设s=j ^ (1 << (k - 1))
                            //dp[k][j ^ (1 << (k - 1)),是将dp定位到,从k城市出发,经过城市子集V[s],回到0号城市所花费的最小距离
                            //怎么定位到城市子集V[s]呢,因为如果从k城市出发的,经过城市子集V[s]的话
                            //那么V[s]中肯定不包含k了,那么在j中把第k个城市置0就可以了,而j ^ (1 << (k - 1))的功能就是这个
                            dp[i][j] = Math.min(dp[i][j], dist[i][k] + dp[k][j ^ (1 << (k - 1))]); //^异或
                            //还有怎么保证dp[k][j ^ (1 << (k - 1))]的值已经得到了呢,
                            //注意所有的计算都是以dp表为准,从左往右从上往下的计算的,每次计算都用到左边列的数据
                            //而dp表是有初试值的,所以肯定能表格都能计算出来
                        }
                    }
                }
            }
        System.out.println(dp[0][V - 1]);
    }
}



编辑于 2019-08-13 17:47:03 回复(2)
哪位大佬可以添加个代码进行解析啊?这个问题一直不会啊!!!  看别人代码也看不懂啊!
发表于 2019-06-16 17:59:55 回复(3)

添加一个简单的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])

发表于 2019-07-15 08:22:32 回复(1)
#include<bits/stdc++.h>
usingnamespacestd;
#define INF 999999
intmain()
{
    intdp[21][21];
    intn,s,i,j,k;
    inttemp,minx;
    while(scanf("%d",&n)!=EOF)
    {
        //int dp[n][n]={0};
        ints[n][1<<(n-1)];
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                if(j!=i) scanf("%d",&dp[i][j]);
                else
                {
                    scanf("%d",&dp[i][j]);
                    dp[i][j]=INF;
                }
            }
        }
        for(i=1;i<n;i++)
        {
            s[i][0]=dp[i][0];
        }
        for(j=1;j<1<<(n-1);j++)
        {
            for(i=1;i<n;i++)
            {
                if(((1<<(i-1))&j)==0)
                {
                    minx=INF;
                    for(k=1;k<n;k++)
                    {
                        if(((1<<(k-1))&j)!=0)
                        {
                            temp=dp[i][k]+s[k][j-(1<<(k-1))];
                            if(temp<minx)
                            {
                                minx=temp;
                            }
                        }
                    }
                }
                s[i][j]=minx;
            }
        }
        minx=INF;
        for(i=1;i<n;i++)
        {
            temp=dp[0][i]+s[i][((1<<(n-1))-1)-(1<<(i-1))];
            if(minx>temp)
            {
                minx=temp;
            }
        }
        printf("%d\n",minx);
    }
}
发表于 2019-08-09 15:33:19 回复(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;
}


发表于 2019-07-24 21:49:41 回复(0)
#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;
}

发表于 2019-10-24 00:59:14 回复(0)
# 运行时,内存超了,贴出来想一起讨论讨论(虽然写得不咋地)
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))

发表于 2019-08-28 11:29:46 回复(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;
}

编辑于 2019-07-07 22:59:39 回复(0)
纯借鉴已有的讨论,增加一点注释
#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;
}


发表于 2019-08-22 20:02:29 回复(0)
这题就是一个经典的NP旅行商问题,解法有很多种,递归可能会超时,递推的动态规划在这里比较推荐。注意他这里城市个数为20,如果直接用普通数组实现dp数组的话,内存一定会超,因为有20个城市,所以数组第二维的大小会达到1048576,这肯定是会超时的,结果也如人所料,如果用普通数组实现dp数组的话,在内存不超的情况下最后测试用例最多通过83%。但是如果使用vector的话就不会,我们可以通过n动态的给vector分配内存,最后100%通过所有测试用例。代码如下:
#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;
    
}

大概解释一下动态规划的递推关系,我们定义dp[j][i]为从点j出发经过除了出发点0以为的集合i(这里的集合i是使用二进制表示的一个集合,比如1,3号点二进制表示维101=5,1,2,3号点可以表示为111=7)因此举个例子,如果有4个城市0,1,2,3号城市,那么从0号城市出发,最后经过1,2,3号城市最后回到0号城市可以表示为:dp[0][{1,2,3}] = dp[0][7] = min{dis[0][1]+dp[1][{2,3}],dis[0][2]+dp[2][{1,3}],dis[0][3]+dp[3][{1,2}]}
dp[1][{2,3}]的意思就是从1号点出发,经过2,3号点最后回到0号点,其他都同理就不再赘述。通过上式不断迭代最后有dp[1][{}]意思就是从1号点出发不经过任何点回到0的最短距离,那么这个距离直接就是dis[1][0]其他以此类推。有了这个递推公式后就可以用动态规划解决了,当然这种方式还是一种用空间换时间的办法,当n很大的时候也会出现无法解决的情况,这就是NP问题的棘手和复杂之处。

发表于 2019-10-03 05:28:36 回复(0)
Java使用贪心算法,但是剪枝效果不大好,出现超时,各位大佬有没有什么优化的建议,还是说这种的用贪心很亏,用动态规划会比较好吗?
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Main{

    public static int minCost = Integer.MAX_VALUE;
    public static int visitedNum = 0;
    public static int[][] array;
    public static boolean[] isVisited;

    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        array = new int[n+1][n+1];
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=n ; j++) {
                array[i][j] = scanner.nextInt();
            }
        }

        isVisited = new boolean[n+1];
        for (int i = 1; i <=n ; i++) {
            isVisited[i] = false;
        }
        //是否访问过的数组
        isVisited[1] = true;
        visitedNum = 1;
        goThrough(1,n,0);

        System.out.println(minCost);

    }

    public static void goThrough(int i,int n,int preCost){
        //1.对访问数组的控制
        //2.计数的控制
        //3.最小代价的控制

        if(visitedNum == n){
            //比较并更新 minCost
            if(preCost+array[i][1]<minCost){
                minCost = preCost + array[i][1];
            }
            return;
        }
        for (int j = 1; j <=n; j++) {
            if(!isVisited[j]){
                //这个点没有被访问过
                preCost = preCost+array[i][j];
                if(preCost > minCost){preCost-=array[i][j];continue;}
                //当前的消耗大于 minCost
                //没有继续下去的意义了,直接退出
                isVisited[j] = true;
                visitedNum++;
                goThrough(j,n,preCost);
                isVisited[j] = false;
                visitedNum --;
                preCost-=array[i][j];
            }
        }
    }
}


发表于 2019-09-22 11:16:58 回复(0)

暴力全排列求解,超时!

from itertools import permutations

def minimum_cost(n, seq):
    possible = list(permutations(range(1, n), n-1))
    end = set()
    for pu in possible:
        if pu not in end and pu[::-1] not in end:
            end.add(pu)
    spend = float('inf')
    for eu in end:
        current = [0] + list(eu) + [0]
        value = 0
        for ci in range(len(current)-1):
            pre, cur = current[ci], current[ci+1]
            value += seq[pre][cur]
        if spend > value:
            spend = value
    return spend


if __name__ == '__main__':
    n = int(input().strip())
    seq = []
    for _ in range(n):
        seq.append(list(map(int, input().strip().split())))
    res = minimum_cost(n, seq)
    print(res)
编辑于 2019-09-07 09:16:28 回复(0)
#include <iostream>
#include <memory>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;
int minvalue = INT_MAX;

void backtrack(vector<vector<int> > arr, vector<int> place, vector<bool> visit,int sum,int n)
{
	if (place.size() == n)
	{
		if (arr[place[place.size() - 1]][0] != 0)
		{
			sum += arr[place[place.size() - 1]][0];
			if (sum < minvalue)
			{
				minvalue = sum;
			}
		}
		return;
	}
	int j = place[place.size() - 1];
	for (int i = 0; i < arr.size(); ++i)
	{
		if (arr[j][i] != 0&&visit[i]==false)
		{
			visit[i] = true;
			sum += arr[j][i];
			place.push_back(i);
			
			backtrack(arr, place, visit, sum, n);
			visit[i] = false;
			sum -= arr[j][i];
			place.pop_back();
			
		}
	}
}


int main(){
	int n;
	cin >> n;
	vector<vector<int> > arr(n, vector<int>(n, 0));
	for (int i = 0; i < n; ++i)//输入
		for (int j = 0; j < n; ++j)
		{
			cin >> arr[i][j];
		}
	vector<bool> visit(n, false);
	vector<int> place;
	place.push_back(0);
	visit[0] = true;
	int sum = 0;
	backtrack(arr, place, visit, sum, n);

	cout << minvalue << endl;
    return 0;
}
贴上递归代码,超时了。
发表于 2019-08-17 15:44:47 回复(0)
这题内存卡得比较死,搞得我怀疑人生,最后发现题目数据应该是有问题,测试过n的范围在19以内。
经典的旅行商问题。
1. G[i][j]表示城市i到城市j的距离;
2. 用dp[i][k]表示当前在城市i,且经过的城市集合为k的最小总路程。集合可以表示为二进制,所以可以用整数k表示。例如j=11001,表示城市集合为{0,3,4}(二进制第0/3/4位为1)。注意,由于dp[i][k]表示为当前在城市i,所以k中必须包含i,即必有(1<<i) & k = 1。(1<<i) & k = 0的状态是不存在的,后面计算时要跳过;
3. 状态转移:dp[j][k | (1<<j)] = min{dp[j][k | (1<<j)], dp[i][k] + G[i][j]},即当前在城市i,经过的城市集合为k时,可以转移到城市j,花费的额外代价是G[i][j]。注意:a) k集合必须包含i,也就是二进制第i位必须为1,即(k>>i) & 1 = 1,或者说(1<<i) & k > 0;b) 因为每个城市只能走1次,k集合不能包含j,否则就说明当前这次转移前已经访问过城市j了,也就是必须满足 (1<<j) & k = 0;
4. 实现时,有2种办法,一种使用递归函数,另一种直接用循环来做。我们发现,状态转移方程中,等式左边的状态k | (1<<j)对应的整数值始终是大于右边的k的(为什么?因为在(1<<j) & k =0时,(1<<j) | k = k + (1<<j) > k),因此我们可以从小到大枚举状态1 ~ (1<<n)-1,对每个状态,考虑该状态可以转移出去的新状态。
5. 最终最小代价为min{dp[i][(1<<n)-1] + G[i][0]},即身处城市i,访问过的集合为{0, 1, 2, 3, ..., n-1}(对应二进制111...111=2^n-1)的总距离,再加上最后从城市i回到城市0的距离之和。我们希望得到上述距离和的最小值。
#include <cstdio>
#include <cstring>

const int MAX = 19;
short G[MAX][MAX];
short dp[MAX][1<<MAX];
 
int main() {
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%hd", &G[i][j]);
            }
        }

		memset(dp, 0x7f7f, sizeof(dp));
		// 初始状态是在城市0,访问集合是{0},即0000...00001
        dp[0][1] = 0;
        for (int k = 0; k < (1<<n)-1; k++) {
        	// 枚举所有状态k;当前已访问城市集合为k,当前在城市i,现在要访问另一个未访问过的城市j
        	for (int j = 0; j < n; j++) {
        		// k集合不能包含j
        		if ((1<<j)&k > 0) {
                    continue;
                }
	            for (int i = 0; i < n; i++) {
	            	// k集合必须包含i
                    if ((1<<i)&k == 0) {
                        continue;
                    } 
                    if (dp[i][k] + G[i][j] < dp[j][(1<<j)|k]) {
                    	dp[j][(1<<j)|k] = dp[i][k] + G[i][j];
                    }
                }
            }
        }
        int ans = 0xfffffff;
        for (int i = 1; i < n; i++) {
        	if (dp[i][(1<<n)-1] + G[i][0] < ans) {
        		ans = dp[i][(1<<n)-1] + G[i][0];
        	}
        }
        printf("%d\n", ans);
    }
    return 0;
}



发表于 2019-08-12 03:37:40 回复(0)
import java.util.HashSet; import java.util.Iterator; import java.util.Scanner;  public class ByteDance004 { public static void main(String args[]){
        Scanner in = new Scanner(System.in);  int n = Integer.parseInt(in.nextLine());  int[][] m = new int[n][n];  for (int i = 0; i < n; i ++){
            String[] str = in.nextLine().split(" ");  for(int j = 0; j <n; j++){
                m[i][j] = Integer.parseInt(str[j]);  }
        }
        HashSet<CityCount> set = new HashSet <>();  CityCount cityCount = new CityCount(0,0);  set.add(cityCount);  int s = 0;  for (int i=0; i < n; i++){ int a = 0;  int b = 0;  int cost = m[i][a] + m[i][b];  Iterator it = set.iterator();  CityCount cc = new CityCount(5,5);  while(it.hasNext()){
                CityCount tem = (CityCount)it.next();  int c = m[tem.getX()][i] + m[tem.getY()][i] - m[tem.getX()][tem.getY()];  if(c < cost){
                    a = tem.getX();  b= tem.getY();  cost = c;  }
                cc = tem;  }
            s+=cost;  set.remove(cc);  set.add(new CityCount(a,i));  set.add(new CityCount(i,a));  }
        System.out.println(s);   }
} class CityCount{ int x;  int y;  public CityCount(int a, int b){ x = a;  y = b;  } public int getX(){ return x;  } public int getY(){ return y;  }
}
发表于 2019-08-11 12:46:34 回复(0)
#蠢递归,只过了50%
#递归判断所有旅行路径的花费最小值
min_p = 100000
visit = []
def dfs(s,deepth,p,map,n):
    if deepth == n:
        global min_p
        min_p = min(p+map[s][0],min_p)
    
    for  j in range(len(map[s])):
        if visit[j] != 1:
            visit[j] = 1
            dfs(j,deepth+1,p+map[s][j],map,n)
            visit[j] = 0

n = int(input())
map = []
for i in range(n):
    row = [int(x) for x in input().strip().split()]
    map.append(row)
for j in range(n):
    visit.append(0)
for i in range(n):
    visit[i] = 1
    dfs(i,1,0,map,n)
print(min_p)
发表于 2019-08-11 11:36:01 回复(1)
自己的机器没问题,可能数据有误或者编译器问题
#include<iostream>
#include<vector>
#include<algorithm>
usingnamespacestd;
 
int** matrix;
 
intP(vector<int> remain)
{
    if(remain.size() == 1)
    {
        returnmatrix[remain[0]][0];//回家
    }
    else
    {
        intsource = remain.back();
        intbest = 50000;
        remain.pop_back();
        for(inti = 0; i < remain.size(); i++)
        {
            vector<int> newremain(remain);
            inttarget = remain[i];
            newremain.erase(newremain.begin() + i);
            newremain.push_back(target);
            intresult = P(newremain) + matrix[source][target];
            if(result < best)
            {
                best = result;
            }
        }
        returnbest;
    }
}
 
intmain()
{
    intN;
    cin >> N;
    matrix = (int**)malloc(N * sizeof(int));
    vector<int> remain;
    for(inti = 0; i < N; i++)
    {
        matrix[i] = (int*)malloc(N * sizeof(int));
        for(intj = 0; j < N; j++)
        {
            inttemp;
            cin >> temp;
            matrix[i][j] = temp;
        }
        remain.push_back(i+1);
    }
    remain.pop_back();
    remain.push_back(0);
    cout << P(remain);
 
    //system("pause");
    return0;
}
发表于 2019-07-31 21:18:08 回复(0)
public class Main{
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] map = new int[n][n];
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                map[i][j] = in.nextInt();
            }
        }
        //dp[i][j]表示从i出发,经过j集合里的所有节点一次回到0点的最小小费
        int V = 1<<(n-1);  //
        int[][] dp = new int[n][V];
        for(int i=0;i<n;i++) {     // 先求dp表第一列
            dp[i][0] = map[i][0];   //每个城市回到起点的距离
        }

        for(int j=1;j<V;j++) {                  // 再求其他列
            for(int i=0;i<n;i++) {              //从i出发,要去包含j = {010101} 的城市
//                dp[i][j] = 100000;               //或者用 0x7ffff表示无穷大
                dp[i][j] = 0x7ffff;
                if(((j >> (i-1)) & 1) == 1) {    //如果已经到过j了,就continue跳出循环
                    continue;
                }
                for(int k=1;k<n;k++) {          //看能不能先到k城市
                    if(((j >> (k-1)) & 1) == 1) {  //能到
                        dp[i][j] = Math.min(dp[i][j], map[i][k] + dp[k][j ^ (1 << (k-1))]);
                    }
                }
            }
        }
        System.out.println(dp[0][(1 << (n-1))-1]);

        /*
         *以下为打印dp表
         */
        System.out.printf("%10d",0);
        for(int j = 0;j < 1 << (n - 1) ;j++){
            System.out.printf("%10d",j);
        }
        System.out.println();
        for(int i = 0;i < n;i++){
            System.out.printf("%10d",i);
            for(int j = 0;j < 1 << (n - 1) ;j++){
                if(dp[i][j] == 0x7ffff) dp[i][j] = -1;
                System.out.printf("%10d",dp[i][j]);
            }
            System.out.println();
        }

    }
}
编辑于 2019-07-06 16:24:53 回复(0)
用例:
5
0 3 4 2 7
3 0 4 6 3
4 4 0 5 8
2 6 5 0 6
7 3 8 6 0
对应输出应该为:
19
你的输出为:
21
这个样例的结果是不是有问题啊,我看了挺久都是21吧,输出
发表于 2019-07-04 16:41:44 回复(0)
这题样例有问题,直接开f[1<<20][20]爆内存,自动生成f[1<<n][n]不会爆内存.至于解析可以搜关键词:哈密尔顿路,旅行商问题,状压dp
发表于 2019-07-04 16:28:43 回复(0)