二维数组中成本有限的最大利润和路径

Question

给定两个大小为n*n的二维矩阵，一个是成本矩阵，另一个是利润矩阵。我们必须找到一条从左上角(0,0)到右下角(n-1,n-1)的路径，它具有最大的利润和成本之和必须小于或等于c。我们只能向右或向下遍历。约束n<= 100 .

Answer 1

1. 计算每条路径的总成本
2. 删除所有具有总成本的路径>C
3. 选择利润最大的剩余路径

注意，由于n <100有最多10000个单元格，每个单元格有2条可能的路径，最大路径数只有20000条。

如果max n明显更大，你需要寻找一个更有效的算法，但对于这些小问题，这个算法是足够的，直接的，易于实现。

Answer 2

用成本矩阵减去利润矩阵。

这样你只有一个矩阵，你现在可以使用Floyd-Warshall算法在加权路径上找到最短路径。

你可以使用Floyd-Warshall与graph = -G(假设没有正值，如果图是倒置的，这可能发生，如果某些节点收入成本= -X，它将不起作用)。这相当于找到最长的简单路径。