所以我刚刚开始更深入地探索动态规划，我遇到了一个我已经有一段时间无法解决的问题.如果您能帮我，我将不胜感激.
如果一个推销员有len(days_travel)天的空闲时间，他知道他在每个城市每天能获得多少收入，那么他可以找到最大收入；
输入列表收入显示他在特定城市的特定日期将获得的收入(例如revenue[0][1] = 2: day 0 and at city 'b'天)，旅行天数是他从一个城市到另一个城市旅行所需的天数(例如days_travel[2][1] = 2 days is required to move from city c to city b天和start天是他出发的城市(第0天)
销售员可以决定他是否会在第101天上班
Ex. (start = 1)
# city: a b c # day:
revenue = [[1, 2, 1], # 0
[3, 3, 1], # 1
[1, 1, 100]] # 2
# city: a b c # city:
days_travel = [[0, 1, 1], # a
[ 1, 0, 1], # b
[ 1, 2, 0]] # c
max revenue = 102
路径:
- 从第0天的城市"b"开始，在那里销售，赚取2美元
- 现在在第一天，早上前往城市c
- 现在在第二天，早上到达C城，在那里工作，赚取100美元
我的步骤:
对days_travel执行Floyd Warshall算法，找到the shortest days from one city to the other，使用上面的例子，结果是相同的矩阵(但在其他矩阵中肯定会有所不同)
def floyd_warshall(days_travel):
nV = len(G)
# Adding vertices individually
for k in range(nV):
for i in range(nV):
for j in range(nV):
G[i][j] = min(G[i][j], G[i][k] + G[k][j])
这让我->；
# city: a b c # city:
days_travel = [[0, 1, 1], # a
[ 1, 0, 1], # b
[ 1, 2, 0]] # c
然后我想循环所有的东西，使用max()，但不起作用
for x in range(len(days_travel)):
for y in range(len(days_travel)):
for day in range(len(revenue)):
如果能帮上忙，我将不胜感激.
Edit:
@然而，MarkKI的代码工作正常.如果我们增加一个约束条件，即销售人员不必从start_city开始，但可以旅行呢
Where a -1 indicates that there is no direct path
# city: 0 1 2 3 # city:
travel_days = [[-1, -1, 3, 1], # 0
[-1, -1, -1, 1], # 1
[1, -1, -1, 1], # 2
[1, 1, 2, -1]] # 3
# city: 0 1 2 3 # day:
revenue = [[1, 2, 3, 4], # 0
[3, 6, 1, 5], # 1
[1, 8, 4, 1], # 2
[1, 10, 4, 5], # 3
[10, 4, 5, 9]] # 4
start = 3
This would mean my route is:
day 0: travel to city 1
day 1: make revenue in city 1 (6)
day 2: make revenue in city 1 (8)
day 3: make revenue in city 1 (10)
day 4: make revenue in city 1 (4)
total revenue: 6+8+10+4 = 28
我认为自上而下的方法是正确的