最优最大行程问题

Question

给定最大的旅行距离(向前和向后的道路)，返回使用最大旅行距离的路线，如果多条相同的路线使用最大的旅行距离，则返回多条路线。

示例1

• 前进路线：[[1,3000],[2,5000],[3,4000],[4,10000],[5,8000]]
• 后向路由：[[1,1000],[2,3000],[3,4000]]
• 最大行程：11000

结果必须是：[4,1]和[5,2]，因为总行程是小于或等于最大距离的11000。

示例2

• 前进路线：[[1,3000],[2,5000],[3,4000],[4,10000]]
• 后向路由：[[1,2000],[2,3000],[3,4000]]
• 最大行程：11000

结果必须是：[2,3]，因为总行程是小于或等于最大距离的9000。

我能够在O(forLength * backLength)中解决这个问题，如下所示：

static void Main(string[] args) {
    int[][] f = new int[5][];
    int[][] b = new int[3][];

    f[0] = new int[] { 1, 3000 };
    f[1] = new int[] { 2, 5000 };
    f[2] = new int[] { 3, 4000 };
    f[3] = new int[] { 4, 10000 };
    f[4] = new int[] { 5, 8000 };

    b[0] = new int[] { 1, 1000 };
    b[1] = new int[] { 2, 3000 };
    b[2] = new int[] { 3, 4000 };

    var result = sol(f, b, 11000);
}

public static List<List<int>> sol(int[][] f, int[][] b,int max) {
    List<List<int>> li = new List<List<int>>();
    int m = 0;
    for (int i = 0; i < f.Length; i++) {
        for (int j = 0; j < b.Length; j++) {
            if (f[i][1] + b[j][1] <= max) {
                li.Add(new List<int>() { f[i][0], b[j][0], f[i][1] + b[j][1] });
                if (m < f[i][1] + b[j][1]) {
                    m = f[i][1] + b[j][1];
                }
            }
        }
    }

    return li.Where(i => i[2] == m).ToList();
}

有人能帮我在时间复杂度方面提高效率吗？

Answer 1

也许我可以给你一个解决方案草案：

• 让我们将“前进”列表命名为fwList，命名为“向后”列表bwList。每个元素按顺序包含一个键和一个值。
• 在元素的值部分(O(N.ln(N))时间复杂性)上使用合并排序或堆排序按升序对两个列表进行排序。
• 对于bwList的每个元素(我们称之为bwElem)，在fwList中查找索引(我们称之为ID)，其中和变得太长(bwElem + fwList[ID] > 11000)。那么[bwElem.key, fwList[ID - 1].key]是解决方案的一部分。
• 将bwList的每个元素的结果连在一起应该会列出您的列表，如果在我的脑海中一切都很清楚的话，您应该有一个O(bwLength * (fwLength)^a)时间复杂度，其中a < 1 (我甚至押注于O(bwLength * ln(fwLength)))。

我认为在此基础上可以对算法进行优化。