http://blog.sina.com.cn/s/blog_6f194ed3010114vt.html

最近建模看到作業(yè)這個(gè)題，一開(kāi)始想了很久。在網(wǎng)上發(fā)現(xiàn)竟然沒(méi)有完備的算法。不過(guò)最后想到一個(gè)可以L(fǎng)ingo實(shí)現(xiàn)的線(xiàn)性規(guī)劃模型。

嚴(yán)格說(shuō)，這不是一個(gè)算法，Lingo是如何實(shí)現(xiàn)0-1規(guī)劃的我并不清楚。有可能也是枚舉法，不過(guò)對(duì)于具體問(wèn)題至少可以解決。因?yàn)槭荰eX編譯的，重新打一遍太麻煩，所以正文用截圖。最后提一個(gè)不成熟的算法。
問(wèn)題重述：有2n個(gè)整數(shù)，試將其平均分為兩組（每組n個(gè)），使兩組元素和的差值最小。




（這里有一點(diǎn)打錯(cuò)了。“從另一個(gè)角度看”后的等式要加絕對(duì)值號(hào)。另外這里要注意需要限定S1較大，之所以如此是因?yàn)閹Ы^對(duì)值號(hào)的min顯然是比較難實(shí)現(xiàn)的。不過(guò)我并不清楚Lingo能不能實(shí)現(xiàn)絕對(duì)值的min...我接觸Lingo才幾天。）






這個(gè)問(wèn)題可以擴(kuò)展到多維變量，并可擴(kuò)展到分為多組。下面就多元、多組的情況討論一個(gè)想法。
一開(kāi)始我設(shè)想了一個(gè)算法，但是感覺(jué)問(wèn)題多多，只能有時(shí)間再深入想：
多元統(tǒng)計(jì)分析中有一個(gè)動(dòng)態(tài)算法：K均值聚類(lèi)。其基本思想是，假定目標(biāo)是聚為k類(lèi)，任意劃分為k組，并分別計(jì)算其均值。然后任選一個(gè)樣本點(diǎn)，計(jì)算其到所有k類(lèi)中心的距離。尋找最小距離，若對(duì)應(yīng)的中心不是自身所在組，則將其調(diào)至改組，再重新計(jì)算各組中心，并重復(fù)本步驟；如果其對(duì)自身所在組中心的距離為最小，則保持不變，繼續(xù)尋找下一個(gè)點(diǎn)，直到所有的點(diǎn)都不需要調(diào)整。
類(lèi)似這個(gè)想法，是否可以反其道行之，每次都將較遠(yuǎn)的元素與組調(diào)在一起。假設(shè)存在一個(gè)調(diào)整，可以使組內(nèi)均值向量更靠近總體均值向量，則進(jìn)行該調(diào)整，直到不存在調(diào)整空間，則停止算法。


這個(gè)問(wèn)題看起來(lái)好像沒(méi)什么實(shí)際意義，純粹是一個(gè)數(shù)字游戲，其實(shí)可以很廣泛的加以應(yīng)用。比如給定你一隊(duì)人馬，每個(gè)人能力不同，如何分配才能保證每組實(shí)力相近以求得公平？或者一些施工人員，你想要他們產(chǎn)生競(jìng)爭(zhēng)激勵(lì)，分組時(shí)就不應(yīng)該偏心而應(yīng)盡可能保證每組實(shí)力接近。該問(wèn)題就是這些實(shí)際問(wèn)題的抽象。

總結(jié)

以上是生活随笔為你收集整理的2n个整数分为两组，使两组和差的绝对值最小的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。