基于旅行时间矩阵，求解给定时间预算下可访问的最大城市数量

这个问题本质是带时间预算约束的开路最长路径问题，由于城市总数只有12个，规模极小，可选择以下几种落地性极强的解法：

解法1：暴力倒序枚举（实现最简单，完全适配12城规模） #

• 核心逻辑：从最多可访问的城市数（12个）开始倒序验证，找到第一个满足时间约束的数值就是答案，不需要验证更小的数量
• 操作步骤：
  1. 先把12个城市的两两旅行时间存为二维距离数组，城市对应编号0-11即可
  2. 从k=12开始倒序遍历到k=1：
     • 枚举所有长度为k的不重复城市排列（起点任意、路径顺序不同总时间不同）
     • 对每个排列累加相邻城市的旅行时间得到总耗时
     • 只要存在任意一个排列的总耗时≤给定预算，直接返回当前k作为结果，终止计算
• 效率说明：12个城市的全排列总数只有4.79亿，且实际预算下通常最多能访问7-9个城市，枚举8个城市的所有排列仅不到2000万次计算，普通消费级电脑可以秒出结果。

解法2：动态规划（效率最高，可拓展到更大城市规模） #

• 状态定义：用dp[mask][u]表示已访问城市集合为mask（mask为12位二进制数，某一位为1代表对应城市已访问），最后停留城市为u时的最小总旅行时间
• 状态转移公式：

  dp[mask | (1<<v)][v] = min(dp[mask | (1<<v)][v], dp[mask][u] + dist[u][v])
  // 其中v是未被mask包含的待访问城市
  

• 初始状态：所有单城市起点的状态dp[1<<u][u] = 0，仅停留在起点没有旅行成本
• 结果统计：从最大的k（二进制mask中1的个数）开始倒序查找，只要存在任意含k个1的mask，对应存在u使得dp[mask][u] ≤ 预算，k就是最大可访问城市数。

解法3：剪枝回溯（平衡实现难度和运行效率） #

• 核心逻辑：从任意起点出发做深度优先搜索，记录当前已访问城市集合、当前累计耗时、当前已访问城市数
• 剪枝规则（大幅减少无效计算）：
  • 当前累计耗时已经超过预算，直接终止当前分支的搜索
  • 当前已访问城市数 + 剩余未访问城市数 ≤ 已经找到的最大可访问数，直接终止当前分支的搜索（不可能得到更优结果）
• 遍历完所有可行路径后即可得到最大可访问数量。

内容的提问来源于stack exchange，提问作者Dharmender Tathgur