例如,给定以下矩阵:
[[[0, 8], [0, 3], [0, 8]],
[[8, 0], [3, 0], [0, 5]],
[[0, 1], [0, 6], [0, 0]]]
其中每个元组的第一个数字是食物,第二个数字是水。我需要从右下角到左上角,我只能向上或向左移动
我需要收集尽可能多的食物和水,这样我才能活得尽可能长。每一天我想要生存,我需要一份食物和一份水,所以如果我能在(7,4)和(6,6)之间做出选择,正确的选择是(6,6),因为这将允许我活6天
如何通过上述矩阵找到最佳路径
我目前的代码如下,但它不起作用(它找到了一个非常高的成本路径,但不是最高的),我不知道如何去做。我不知道如何开始实现它,尽管我被告知要避免递归
def maxSuppliesPath(matrix):
n = len(matrix) - 1
bestPath = matrix
# Initialize first column of bestPath array
for i in range(1, n + 1):
if bestPath[i][0] == 0:
bestPath[i][0] = bestPath[i - 1][0]
else:
bestPath[i][0] = (bestPath[i][0][0] + bestPath[i - 1][0][0], bestPath[i][0][1] + bestPath[i - 1][0][1])
# Initialize first row of bestPath array
for j in range(1, n + 1):
if bestPath[0][j] == 0:
bestPath[0][j] = bestPath[0][j - 1]
else:
bestPath[0][j] = (bestPath[0][j - 1][0] + bestPath[0][j][0], bestPath[0][j - 1][1] + bestPath[0][j][1])
# Construct rest of the bestPath array
for i in range(1, n + 1):
for j in range(1, n + 1):
if min(bestPath[i][j - 1][0] + bestPath[i][j][0], bestPath[i][j - 1][1] + bestPath[i][j][1]) > min(
bestPath[i - 1][j][0] + bestPath[i][j][0], bestPath[i - 1][j][1] + bestPath[i][j][1]):
bestPath[i][j] = (bestPath[i][j - 1][0] + bestPath[i][j][0], bestPath[i][j - 1][1] + bestPath[i][j][1])
else:
bestPath[i][j] = (bestPath[i - 1][j][0] + bestPath[i][j][0], bestPath[i - 1][j][1] + bestPath[i][j][1])
return min(bestPath[n][n][0], bestPath[n][n][1])
解决问题的第一步是了解如何遍历矩阵。下图显示了从起点到其他点的距离
请注意,等距点排列在对角线上。给定表示一条对角线的
set
(称之为a),下一条对角线上的点(称之为B)如下所示:在本例中,表示对角线的集合应如下所示:
下图显示了可以使用多少条不同的路径到达矩阵中的每个点。路径的数目与Pascal's triangle中的数目相同。就这个问题而言,唯一重要的是数量的快速增长,因此我们需要减少数量
为了减少路径计数,我们需要在遍历矩阵时剔除非生产性路径。这是通过比较元组来实现的,每个元组由食物和水组成。元组
例如,考虑矩阵中的中心位置。我们可以通过向上移动然后向左移动,或者向左移动然后向上移动来达到这一点。向上移动会产生(3,5)的产量(食物、水),而向上移动会产生(3,6)。(3,6)占主导地位(3,5),所以我们只需要考虑(3,6)。所以在两次移动之后,我们的情况如下所示。注意,我们在中心位置只有一个元组,而不是Pascal三角形预测的两个元组(F,W)
支配元组(f,w)
iffF >= f
和W >= w
经过三次移动,我们的情况如下所示。第三条对角线上的每个点有两个元组。这是必要的,因为其中一个元组有更多的食物,而另一个元组有更多的水,所以两者都不能支配另一个元组
四步之后,我们有四个可能的答案,选择最好的答案只需比较每个元组的
min(food, water)
相关问题 更多 >
编程相关推荐