3

我有一个编号元素 1 到 N 的列表，它们适合从 1 开始的数轴上的位置。我也对这些元素有限制：

  • 元素 1 位于位置 1，元素 N 必须位于 >= 元素 N-1 的位置。（即元素 2 可能在位置 1，元素 3 在位置 7，元素 4 在位置 8（但不是位置 5））
  • 某些元素必须在一定距离内才能在线。
  • 某些元素必须至少与其他元素保持一定距离就行了。

我的目标是返回一个整数，表示元素 1 和元素 N 之间的最大跨度。如果没有可能的阵容，则返回 -1，如果元素可以相隔任意距离，则返回 -2。

我得到：

  • 元素数量
  • 一个 withinArray[][] 其中 withinArray[x][y] = 距离元素 x 和 y 必须在行内。任何零值表示没有约束。
  • 一个 atLeastArray[][] 其中 atLeastArray[x][y] = 距离元素 x 和 y 必须在线上分开。任何零值表示没有约束。

一个示例输入是：4 个元素，withinArray[1][3] = 10、withinArray[2][4] = 20 和 atLeastArray[2][3] = 3。（所有其他数组值为零）。

此输入的返回值为 27。（元素 1 位于位置 1，元素 2 位于位置 8，元素 3 位于位置 11，元素 4 位于位置 28）

到目前为止，我想出了这个：

for (int i = 1; i < n; i++) {
    for (int j = 1; j < atLeastArray.length; j++) 
        if (j == i)
            positions[i] = positions[j] - atLeastArray[i][j];
    for (int j = 1l j < withinArray.length; j++) 
        if (j == i) 
            positions[j] = positions[i] + withinArray[i][j];
}
return positions[n] - positions[1];

这为我给出的示例提供了正确的答案，但我不相信它在每种情况下都有效，而且我不确定如何定义不可能的情况或元素是否可以相距任何距离。

4

1 回答 1

0

让我们从线性规划的角度来考虑这个问题。我们有变量 x_1、...、x_n 和一堆形式为 x_i <= x_(i+1)、x_i - x_j <= w_{ij} 和 x_i - x_j >= a_(ij) 的约束。

注意当我们对一个变量进行傅里叶-莫茨金消除时会发生什么——也就是说，在它出现的每个方程中隔离它，形成两组不等式，比如 x_i <= foo_k 对于各种 k 和 x_i >= bar_l 对于各种l，然后删除所有涉及 x_i 的约束并将它们替换为每个 k 和 l 的约束 bar_l <= foo_k。

您将获得与以前相同形式的更多约束！请注意，如果您知道 x_i - x_j <= a 和 x_i - x_j <= b，则可以得出结论 x_i - x_j <= min(a,b) 并忘记之前的两个约束。所以你永远不需要超过 n^2 个约束。

所以只需消除除 x_1 和 x_n 之外的所有变量。最后会有两个约束，即 x_n - x_1 >= a 和 x_n - x_1 <= b。检查 a <= b 并且 b 不是无穷大，你应该很好。

嗯，如果有人能教我如何在这件事上写数学，我将不胜感激:)

于 2012-12-05T03:06:05.340 回答