發現一些

Question

我有編號的元件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位，11位元件3，和元件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]; 

這讓我對我所給出的例子正確的答案，但我不覺得有信心它工作在任何情況下，我不知道如何界定的情況下，當它的不可能或者如果元素可以相隔任何距離。

Answer 1

讓我們從線性規劃的角度思考這個問題。我們有變量x_1，...，x_n和一組約束形式x_i < = x_（i + 1），x_i_x_j < = w_ {ij}和x_i_x_j> = a_（ij）。

注意當我們對一個變量進行傅立葉-Motzkin消除時會發生什麼---也就是說，在它出現的每一個方程中隔離它，形成兩組不等式，形成兩組不等式，如x_i < = foo_k對於各種k和x_i> = bar_l，然後移除所有涉及x_i的約束，並用約束條件bar_l < = foo_k替換它們，對於每個k和l。

您將得到更多的與以前相同的表單限制！請注意，如果您知道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。檢查一下< = b，那b不是無窮大，你應該很好。

呃，如果有人能教我如何寫這個東西的數學，我會很感激:)