1
問題描述的最大絕對差異：
給n變量和k對。通過將1至n的值分配給每個變量，變量可以不同。每對p包含2個變量，並且讓p中的2個變量之間的絕對差值爲abs(p)。定義差異的上限爲U=max(Abs(p)|every p)。最小化在對數字
找到一個最小化的作業。
Limit:
n<=100
k<=1000
每個變量在配對列表中至少出現2次。
A problem instance:
Input
n=9, k=12
1 2 (meaning pair x1 x2)
1 3
1 4
1 5
2 3
2 6
3 5
3 7
3 8
3 9
6 9
8 9
Output:
1 2 5 4 3 6 7 8 9
(meaning x1=1,x2=2,x3=5,...)
闡釋：將導致的x1=1,x2=2,x3=3,...一種分配在U=6（3 9具有greastest絕對值）。輸出分配將得到U=4，最小值（更改的配對：3 7 => 5 7, 3 8 => 5 8等，並且3 5不更改，在這種情況下，每對配對爲abs(p)<=4）。
有一個重要的點：要達到最佳分配，必須改變具有最大絕對值的對中的變量。
在此基礎上，我曾經想過一個貪心算法：
1)Assign every x to default assignment (x(i)=i)
2)Locate pairs that have largest abs and x(i)'s contained in them.
3)For every i,j: Calculate U. Swap value of x(i),x(j). Calculate U'. If U'<U, stop and repeat step 3. If U'>=U for every i,j, end and output the assignment.
然而，這種方法有一個重大缺陷，如果我們需要一個這樣的分配：
x(a)<<x(b), x(b)<<x(c), x(c)<<x(a)
，我們必須換在兩個步驟中，如：x(a)<=>x(b)，然後x(b)<=>x(c)，那麼有可能x(b)<<x(a)在第一步中其abs已經變得大於U並且交換失敗。
是否有任何有效的算法來解決這個問題？
我在這裏沒有看到問題，也沒有編寫代碼或對問題的解釋。相反，我看到什麼看起來像一個家庭作業。 –
所以你想最小化每一對內的最大差異？ – user1354999