首页 > 试题广场 > 毕业旅行问题
[编程题]毕业旅行问题
  • 热度指数:9079 时间限制: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 回复(14)
不会,参考了前面的答案,为其添加了注释
#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 回复(2)
这题就是一个经典的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 回复(1)

添加一个简单的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 回复(2)
哪位大佬可以添加个代码进行解析啊?这个问题一直不会啊!!!  看别人代码也看不懂啊!
发表于 2019-06-16 17:59:55 回复(4)
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]);
    }
}

发表于 2020-09-13 05:46:32 回复(0)
好不容易写了个回溯+剪枝,还只过了50%,动态规划现场想真的想不出来
发表于 2020-04-30 22:06:33 回复(0)
#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<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;

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)
字节跳动都要求会状压DP了吗,没学过ACM的表示好慌。基于起始点不会在DP过程中再被访问的思想,做了一点空间上的小优化,比常见的答案要少用一半的内存。
#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;
}


编辑于 2021-01-17 02:48:47 回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
/**
 *动态规划————旅行商问题
 初学编程,整理前辈代码,加上了自己的理解,供大家参考
 * @author WangJie
 *
 */
public class Main {
    
    //读数器
    public static int reader(StreamTokenizer st) throws IOException {
        st.nextToken();
        return (int)st.nval;
    }
    public static void main(String[] args) throws IOException {
        
        //写入数据
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        int n = reader(st);
        int[][] cost = new int[n][n];
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < n;j++) {
                cost[i][j] = reader(st);
            }
        }
        
        /*
         分析:
         假设有0,1,2,3四个城市,起点不会影响结果,因此选城市0为起点,创建一个二维数组dp[][],用二维数组元素的值代表最低花费,用行坐标代表起点城市,列坐标代表接下来要去的城市(注列坐标用二进制表示,如接下来去1,3城市,则使二进制数第一三位为1,即用101表示)。
         因此以0为起点的最低花费可表示为dp[0][111];
         
         以0为起点三种情况:
         以0为起点,再进一步选定3为起点,最低花费可表示为cost[0][3]+dp[3][011];
         以0为起点,再进一步选定2为起点,最低花费可表示为cost[0][2]+dp[2][101];
         以0为起点,再进一步选定1为起点,最低花费可表示为cost[0][1]+dp[1][110];
         
         取上面三个式子最小值,假设第一种最小,即cost[0][3]+dp[3][011]最小
         
         以0为起点,再进一步选定3为起点两种情况:
         以0为起点,再进一步选定3为起点,再进一步选定2为起点,最低花费可表示为cost[0][3]+cost[3][2]+dp[2][001];
         以0为起点,再进一步选定3为起点,再进一步选定1为起点,最低花费可表示为cost[0][3]+cost[3][1]+dp[1][010];
         
         取上面两个式子最小值,假设第一种最小,即cost[0][3]+cost[3][2]+dp[2][001]最小
         最低花费可表示为cost[0][3]+cost[3][2]+cost[2][1]+dp[1][000]
         */
        
        int all = 1 << (n -1); //确定dp列数:000,001,010,100,011,101,110,111。2^(n-1)个
        int[][] dp = new int [n][all]; //建立dp
        
         //由以上分析知,最终结果会出现dp[i][000],即从此点回到起始点的花费,以此初始化数组
        for(int i = 0;i < n;i++) { 
            dp[i][0] = cost[i][0];
        }
        
        for(int j = 1;j < all;j++) { /* j=1(在以上分析的例子中二进制为001)代表最后经过城市1
                                         j=2(在以上分析的例子中二进制为010)代表最后经过城市2
                                         j=3(在以上分析的例子中二进制为011)代表最后经过城市1和2
                                         …………*/
            for(int i = 0;i < n;i++) { //在以上分析的例子中,当j = 1时,此循环代表遍历dp[i][001]
                dp[i][j] = Integer.MAX_VALUE; //给元素设定一个最大值,方便寻找更小的值
                if(((j >> (i - 1)) & 1) == 0) { /*此式子代表当dp[i][j]当j中的二进制数从右面数第i个数为零时,才进行后面运算,因为i代表以该城市为起点,后面不能再经过该城市*/
                    for(int k = 1;k < n;k++) { //查找j代表经过的城市
                        if(((j >> (k - 1)) & 1) == 1) { /*在以上分析的例子中,如j为101,则当k=1和3时,条件为true*/
                            dp[i][j] = Math.min(dp[i][j], cost[i][k] + dp[k][j^(1 << (k - 1))]); /*其中式子:cost[i][k] + dp[k][j^(1 << (k - 1))]代表从城市i出发,然后经过城市k,的最小花费,对应以上分析的例子中“以0为起点三种情况:”*/
                        }
                    }
                }
            }
        }
        System.out.println(dp[0][all - 1]); /*在以上分析的例子中all-1转化成二进制,为111,此代码代表以0为起点,经过1,2,3城市最低花费*/
    }
}

发表于 2020-10-26 21:34:10 回复(0)
自上而下的dp版本
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);
    }
}


发表于 2020-07-11 16:57:46 回复(0)

动态规划解决问题:

通过率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))
发表于 2020-06-12 01:31:16 回复(1)
这题卡内存卡得好蠢。。。而且数据有点弱吧。。。说好的n<=20,结果开到(1<<20)内存超了,(1<<19)能过
发表于 2020-03-05 10:50:10 回复(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 <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)
这题的空间限制是胡闹的吗?32M? 一个int dp[1<<20][20]的 大小大概是20*4*MB ,32MB怎么可能够用?
发表于 2021-03-01 12:44:59 回复(0)
旅行商问题,记得是一个典型的NP完全问题!!
这个动态规划也是要遍历所有的可能路径求解,时间复杂度很高。
#include <iostream>
#include <vector>
#include <stdint.h>
using namespace std;

int travel(vector<vector<int> > &m) {
    const int N = (1<<m.size())-1;
    vector<vector<int> > dis(m.size(), vector<int>(N+1, 999999));

    // t代表路径经过城市集合,不包括起点
    for(int i = 0; i < m.size(); i++) {
        int k = (1<<i);
        dis[i][k] = m[0][i];
    }
    for(int t = 1; t < N; t++) {
        for(int i = 0; i < m.size(); i++) {
            for(int k = 1; k < m.size(); k++) {
                if(k == i) continue;
                int kv = (1<<k), iv = (1<<i);
                // t必须包括k,但不能包括i
                if((t&iv) != 0 || (t&kv) == 0) continue;
                int x = dis[k][t] + m[k][i];
                dis[i][t|iv] = min(x, dis[i][t|iv]);
            }
        }
    }
    return dis[0][N];
}

int main(void) {
    int n = 0;
    cin>>n;
    vector<vector<int> > m(n, vector<int>(n));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin>>m[i][j];
        }
    }
    int s = travel(m);
    cout<<s<<endl;
    return 0;
}


发表于 2020-11-01 08:37:33 回复(0)
#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin >> n;
	int l = 1 << (n - 1);
	vector<vector<int>> vv(n, vector<int>(n, 0));
	vector<vector<int>> v(n, vector<int>(l, INT_MAX/2));
	for (int i = 0; i < n; i++) {
		for (int ii = 0; ii < n; ii++) {
			cin >> vv[i][ii];
		}
	}
	for (int i = 0; i < n; i++) {
		v[i][0] = vv[i][0];
	}
	for (int j = 1; j < l; j++) {
		for (int i = 0; i < n; i++) {
			if (((j >> (i - 1)) & 1) == 0) {
				for (int m = 1; m < n; m++) {
					if (((j >> (m - 1)) & 1) == 1) {
						v[i][j] = min(v[i][j], vv[i][m] + v[m][j ^ (1 << (m - 1))]);
					}
				}
			}
		}
	}
	cout << v[0][l - 1];

}

发表于 2020-09-08 09:50:14 回复(0)