如何最大化您作为推销员的利润？ Python动态编程

Question

给出了两个列表，您必须找到最佳的城市以最大程度地提高收入。

假设您从第0天开始

第一个列表Money_day = [[1，1]，[99，2]]表示您在特定城市的特定日期将赚钱的金额。金钱[i] [j]代表我在城市jeg Money_day [0] [0]赚钱的金额，将是您在城市0的第0天赚钱的金额。

。

第二个列表youse_travel = [[[0，1]，[none，0]]表示您需要从城市到城市需要的天数。可能的_travel [i] [j]将是从城市到城市jeg stoble_travel [0] [1]需要多长时间的时间，这意味着要从城市0到城市1。从城市到城市J

的道路

• 在某个城市销售将需要一整天（如果您在第2天出售，您将无法在第3天之前再次出售或再次出售
• 您可以访问同一城市再次出售
• 旅行也将需要X天（如果您在第2天开始旅行2天，您将在第4天之前做任何事情）

有以下代码，这些代码似乎对更大的列表不起作用。

def most_money(start, money_day, possible_travel):
    tab = [-10] * len(money_day)
    for days in possible_travel[start]:
        tracker = 0
        if possible_travel[start][days] is None:
            continue 
        else:
            tab[possible_travel[start][days]] = max(money_day[days][possible_travel[start][days]] + tracker, tab[possible_travel[start][days]])
            tracker += tab[possible_travel[start][days]]
    return memo

目前，我 我也不确定递归是否是一种更好的方法。

Answer 1

您可以像这样分解它：每天，您要么呆在同一个城市，这意味着您在那天的利润使第二天的利润重新开始在同一城市，要么前往另一个城市，这意味着您旅行时间后，在那个城市重新开始。

在代码中，将Money_day和可能的作为简单性的全局常数，并假设前往另一个城市的旅行时间为0：

last_day = len(money_day) - 1
cities = set(range(len(possible_travel)))

def most_money(day, city):
    """Return how much money is left to be made, 
    if the current state is given by day, city."""
    if day > last_day:
        return 0
    if day == last_day:
        return money_day[day][city]  
    return max([money_day[day][city] + most_money(day + 1, city)] +
               [most_money(day + possible_travel[city][next_city], next_city) 
                for next_city in cities - {city}
                if possible_travel[city][next_city] is not None])