毕业旅行问题

动态规划解决问题：

通过率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 <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;
}

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

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);
}

"""
方法思路：
1.问题分析：对于城市的履行方案，是有限个方案里面选最佳，所以我们可以采用动态规划来做
2.动态规划的状态定义：dp[mask][u],其中mask表示已经访问过的城市集合，u表示当前访问的城市
dp[mask][u]表示从城市u触发，经过mask表示的城市合集，最后回到起点的最小花费
3.状态转移：对于每一个状态(mask,u),遍历所有未访问的城市v,更新dp[mask | (1<<v)][v]
为dp[mask][u] + m[u][v]的最小值
4.初始化和结果:初始化时，dp[(1 << n) - 1][0](从起点北京出发，没有访问其他城市时我的花费0)
最终结果是dp[(1<<n)-1][0],访问其他节点回到起点的最小值
"""


def solve():
    import sys

    input = sys.stdin.read().split()  # 读取所有输入数据并拆分成列表
    ptr = 0  # 初始化指针，用来逐个访问输入列表中的元素

    # 读取城市数量n
    n = int(input[ptr])
    ptr += 1

    # 初始化车票价格矩阵m
    m = []
    for _ in range(n):
        # 读取每一行车票的价格，并转化为整数列表
        row = list(map(int, input[ptr : ptr + n]))
        m.append(row)
        ptr += n

    # 初始化动态规划表dp
    size = 1 << n  # 结算状态的总数，即2^n
    INF = float("inf")
    # dp[mask][u]表示在状态mask下，当前所在城市u的最小花费
    dp = [[INF] * n for _ in range(size)]
    # 初始状态，从北京（城市0）出发，仅访问过北京
    dp[1][0] = 0

    # 动态规划填表过程
    for mask in range(size):  # 遍历所有可能的状态mask
        for u in range(n):  # 遍历所有当前所在城市u
            if dp[mask][u] == INF:  # 如果当前状态不可以到达，跳过
                continue
            for v in range(n):  # 遍历所有可能的下一城市v
                if not (mask & (1 << v)):  # 如果城市没有被访问过
                    new_mask = mask | (1 << v)  # 更新状态，标记城市v已经被访问

                    # 新状态花钱少，选择新状态
                    if dp[new_mask][v] > dp[mask][u] + m[u][v]:
                        dp[new_mask][v] = dp[mask][u] + m[u][v]

    # 计算回来的最小花费
    full_mask = (1 << n) - 1  # 全访问状态，所有城市都已经被标记
    min_cost = INF  # 初始化最小花费为无穷大
    for u in range(1, n):  # 遍历除了北京以外的所有城市
        # 计算从城市u回到北京的花费，并更新最小花费
        if dp[full_mask][u] + m[u][0] < min_cost:
            min_cost = dp[full_mask][u] + m[u][0]
    # 答案
    print(min_cost)


solve()