分發數字兩種「容器」，並儘量減少它們的和

的差異假設有N個數讓說，我們有以下4個號碼15,20,10,25分發數字兩種「容器」，並儘量減少它們的和

有兩個容器A和B，我的工作是分配數字給他們，以便每個容器中的數字總和差別最小。

在上面的例子中，A應具有15 + 20和B應該有10+ 25.因此，差= 0

我想的方法。它似乎工作，但我不知道爲什麼。

排序編號列表中第一個降序排列。在每一輪中，取出最大數量爲並放到容器中的總和較少。

順便說一下，是可以通過DP解決？ THX

2011-12-23 Bear

請參閱：[分區問題]（http://en.wikipedia.org/wiki/Partition_problem）。此外，[this]（http://www.americanscientist.org/issues/issue.aspx?id=3278&y=0&no=&content=true&page=4&css=print）是一個很好的閱讀。 – Ani 2011-12-23 03:57:19

看到這個問題：http：// stackoverflow。com/questions/5292162/partition-problem – 2011-12-23 06:42:39

可能重複[分兩部分表示它們的總和最接近] [http://stackoverflow.com/questions/4479479/divide-list-in-two-parts-那他們的總和最接近對彼此） – 2011-12-23 07:28:08

事實上，你的方法並不總是工作。想想你的方法2,4,4,5,5。結果將是(5,4,2)(5,4)，而最好的答案是(5,5)(4,4,2)。
是的，它可以被通過動態規劃解決。這裏是一些有用的鏈接：

教程和代碼：http://www.cs.cornell.edu/~wdtseng/icpc/notes/dp3.pdf
做法：http://people.csail.mit.edu/bdean/6.046/dp/（然後單擊Balanced Partition）
更重要的是，請注意，如果問題的規模是該死的大（比如你有500萬數字等），你不會想要使用需要太大矩陣的DP。如果是這樣的話，你想用一種蒙特卡洛算法：
1. 鴻溝n個數分成兩組隨機（或使用你的方法在這一步，如果你喜歡）;
2. 選擇從每個組
  一個數，如果（交換這兩個數目減少之和的差）交換它們;
3. 重複步驟2，直到「沒有交換髮生了很長一段時間」。
你不想想到這個方法總是可以用最好的答案工作了，但我知道，在合理的時間和內存內超大規模解決這一問題的唯一途徑。

來源

2011-12-23 07:04:17 Skyler

dp是否適用於負值？ – FUD 2011-12-23 12:09:19

@ChingPing是的。 – Skyler 2011-12-23 12:10:50

能否詳細說明一下，因爲我真的不耐煩地完全閱讀它，並且我看到「T [x]將是真的當且僅當在紙張的開始處有一個具有總和x的數字的子集」。我認爲dp的基本思想也是揹包填充問題。 – FUD 2011-12-23 13:36:28

分發數字兩種「容器」，並儘量減少它們的和

回答

相關問題