n個有重複數,求其一種排列使得前綴和絕對值的最大值最小,有較好的演算法嗎?

如題。


我來解釋一下 @趙金昊 構造的例子。

假設已知的數中有且僅有一個負數 -2N,另外的數都是正數,且和為 2N。

如果這些正數中有若干個相加等於 N,那麼就可以構造這樣一個排列:相加等於 N 的數排在前面,然後排 -2N,再把另外一些數排在後面。這樣,「前綴和的絕對值」最大是 N。

如果這些正數中沒有任意一個子集相加等於 N,則上面這件事做不到,「前綴和的絕對值」必然在某個時刻大於 N。

而「判斷一些數中有沒有一個子集相加等於給定值」(稱為「子集和問題」)是一個 NPC 問題,題主的問題可以化歸為子集和問題,所以沒有多項式時間的解。


補充一些細節。

首先證明「子集和問題」可以歸約為「均分問題」。子集和問題是給定 n 個正整數和一個正整數 m ,問能否從 n 個數中取出一些數使其和為 m 。用 (A, m) 表示子集和問題的輸入,其中 A 是長度為 n 的正整數列。

均分問題是給定 n 個正整數,問能否將這些數分成兩部分,使它們各自的和相等。用 A 表示均分問題的輸入,其中 A 是長度為 n 的正整數列。

注意均分問題顯然可以歸約為子集和問題(不過這不是我們需要的),但反過來則需要說明。任給一個子集和問題的輸入 I=(A, m) ,計算 A 中所有數之和 S ,將 J=A?{S+m+1, 2S-m+1} 作為均分問題的輸入,則 I 滿足子集和問題,當且僅當 J 滿足均分問題。這就完成了將子集和問題歸約為均分問題的過程。

接下來將均分問題歸約為題主所述的問題。題主的問題不是判定性問題,但是很容易找到相應的判定性問題:給定 n 個整數和一個整數 m ,問能否將 n 個數重排,使新數列前綴和絕對值的最大值小於等於 m 。不妨將該問題稱為「前綴和問題」。用 (A, m) 表示前綴和問題的輸入,其中 A 是長度為 n 的正整數列。

之後將均分問題歸約為前綴和問題,這個其他回答已經提到了。任給一個均分問題的輸入 I=A ,計算 A 中所有數之和 S ,將 J=(A?{-S}, S/2) (其中 S/2 取下整)作為前綴和問題的輸入,則 I 滿足均分問題,當且僅當 J 滿足前綴和問題。歸約過程完成。

因為子集和問題是 NPC 問題,所以前綴和問題是 NP-hard 問題(實際上前綴和問題也是 NP 問題,只要將 n 個數重排的順序作為證書即可;因此,前綴和問題是 NPC 問題),從而不太可能在多項式時間內解決。

題主的問題比「前綴和問題」(指剛剛提到的判定性問題)要強,因為若求得前綴和絕對值最大值的最小值,立即可以解決「前綴和問題」。所以題主的問題也不太可能在多項式時間內解決。


NPC的,別想啦。

搞個-2N,以及若干個和為2N的數,不是分分鐘變成子集和問題嘛。

所以解題思路只有一種,就是看數的大小。如果不超過10的話還是可做的……


數據範圍小的時候可以考慮暴搜O(n!)或者去dp一下——dp[現在已經用了哪幾個數],保存值為前綴最大值O(2^n*n)。


既然是NPC那我就可以放心大膽推薦退火和遺傳了


感覺退火可做。


推薦閱讀:

為什麼 Dev C++ 特別流行?
如何評價JSOI2017round1 ?
有哪些適合信競退役唱的歌?
如何評價NOIP2017提高組複賽?
信息學競賽中有哪些令人高呼「還有這種操作」的技巧?

TAG:演算法 | 計算機科學 | OI | ACM競賽 |