首页 > 试题广场 >

毕业旅行问题

[编程题]毕业旅行问题

热度指数：14411 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

输入描述:

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

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

输出描述:

最小车费花销 s

示例1

输入

输出

说明

共 4 个城市，城市 1 和城市 1 的车费为0，城市 1 和城市 2 之间的车费为 2，城市 1 和城市 3 之间的车费为 6，城市 1 和城市 4 之间的车费为 5，依次类推。假设任意两个城市之间均有单程票可购买，且票价在1000元以内，无需考虑极端情况。

算法知识视频讲解

Python

自来熟的布莱克又在摸鱼

动态规划解决问题：

通过率50% ，其余超时

题目难点在于状态定义，关键点：题目理解。题目中要求回到北京，是一个定义状态麻烦的点。

状态定义： $dp(i,nodes)$ 代表由 i 城市出发，经过 nodes 里面所有节点，回到北京的最低费用。

状态转移方程： $dp(i,nodes) = min(C_{i}^{k} + dp(k , V')\ for \ k \ in \ nodes)$

$C_i^k \ 表示由城市i \ 到城市 k\ 的花销$ ， $V' 是 \ V - k$

边界方程：当 $len(nodes) == 1 \ 时$ ，花销直接可以定下来， $dp(i,nodes) = C_i^{nodes[0]} + C_{nodes[0]} ^ 0$

算法流程：

1. 根据输入构建花销矩阵 $Cost$ ,
2. 构建除北京外的节点列表 $\ nodes$
3. 返回 $dp(0 , nodes)$ 结果即可

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)