基于Python的类旅行商动态规划问题：求解销售员最大收益

嘿，刚好之前琢磨过类似的DP问题，给你梳理下怎么一步步搞定这个销售员的最大收益问题～

首先得把问题的核心拎清楚：我们要在给定的天数里，决定每天是待在当前城市赚当天的钱，还是花几天时间跑到另一个城市，换个地方赚更多的钱，最终让总收益最大化。

第一步：定义DP状态 #

先给动态规划找个“状态”，这是DP问题的灵魂。我们可以这么定义：

• dp[i][j] 表示第i天结束时，销售员在城市j手里能拿到的最大总收益。

这里的i从0开始，到总天数减1（比如总共有5天空闲，那i就是0-4）；j是城市的索引（比如0代表城市a，1代表b，以此类推）。

第二步：初始化状态 #

题目说第0天从指定起始城市出发，那我们先把初始状态铺好：

• 第0天在起始城市start_city，自然能拿到当天的收益，所以dp[0][start_city] = revenue[0][start_city]。
• 第0天不可能在其他城市，所以其他dp[0][j]（j≠start_city）都设成负无穷，表示这个状态根本达不到，避免干扰后续的最大值计算。

第三步：状态转移（最关键的一步） #

接下来就是每天的状态怎么推导出下一天的状态，分两种情况考虑：

情况1：留在当前城市 #

如果前一天已经在城市j了，那今天继续待在这儿，收益直接加上当天的revenue[i][j]就行：

dp[i][j] = dp[i-1][j] + revenue[i][j]

情况2：从其他城市旅行过来 #

假设我们想在第i天到城市j，那得看看从其他城市k过来需要多久。比如从k到j需要t = days_travel[k][j]天，那意味着我们得在i - t天结束时还在k，然后花t天赶路（这t天没收益），第i天到达j并赚当天的钱。

这时候的收益就是dp[i - t][k] + revenue[i][j]，我们要把这个值和当前的dp[i][j]比，取大的那个更新进去。

⚠️ 注意：这里一定要检查i - t >= 0，不然时间不够赶路，根本到不了。

第四步：算最终结果 #

等把所有天数的状态都算完，最后一天（也就是total_days-1天）所有城市的dp值里，最大的那个就是我们要的最大收益。

举个实际例子帮你理解 #

假设：

• 总共有5天空闲（0-4天）
• 起始城市是0（城市a）
• 每日各城市收益revenue：

  [
    [3, 2, 1],  # 第0天：a赚3，b赚2，c赚1
    [4, 3, 2],  # 第1天
    [5, 4, 3],  # 第2天
    [6, 5, 4],  # 第3天
    [7, 6, 5]   # 第4天
  ]
  

• 城市间旅行天数days_travel：

  [
    [0, 1, 2],  # a到a要0天，a到b要1天，a到c要2天
    [1, 0, 1],  # b到a要1天，b到b要0天，b到c要1天
    [2, 1, 0]   # c到a要2天，c到b要1天，c到c要0天
  ]
  

按照步骤算下来，最后一天的dp值是[25,24,22]，最大的25就是一直待在城市a的总收益，符合预期。

代码实现（Python） #

我把上面的逻辑写成了代码，你可以直接用，也可以根据自己的需求调整：

def max_salesman_revenue(total_days, revenue, days_travel, start_city):
    num_cities = len(revenue[0])
    # 初始化DP数组，用负无穷标记不可达状态
    dp = [[float('-inf')] * num_cities for _ in range(total_days)]
    # 第0天在起始城市的初始收益
    dp[0][start_city] = revenue[0][start_city]
    
    for i in range(1, total_days):
        for j in range(num_cities):
            # 情况1：留在当前城市
            if dp[i-1][j] != float('-inf'):
                dp[i][j] = dp[i-1][j] + revenue[i][j]
            
            # 情况2：从其他城市旅行过来
            for k in range(num_cities):
                if k == j:
                    continue  # 自己到自己不用考虑，情况1已经覆盖
                travel_days = days_travel[k][j]
                if i >= travel_days:
                    prev_day = i - travel_days
                    if dp[prev_day][k] != float('-inf'):
                        candidate = dp[prev_day][k] + revenue[i][j]
                        if candidate > dp[i][j]:
                            dp[i][j] = candidate
    
    # 返回最后一天的最大收益
    return max(dp[-1])

测试一下刚才的例子：

total_days = 5
revenue = [
    [3,2,1],
    [4,3,2],
    [5,4,3],
    [6,5,4],
    [7,6,5]
]
days_travel = [
    [0,1,2],
    [1,0,1],
    [2,1,0]
]
start_city = 0
print(max_salesman_revenue(total_days, revenue, days_travel, start_city))  # 输出25

如果有特殊情况（比如旅行天数为0，或者总天数只有1天），代码也能处理，你可以放心用～

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