PartitionProblem - 找到最優的子集

Question

我需要找到最優的子集，解決分區問題後，使用動態規劃僞多項式時間算法。

更具體地說，我不能讓這個答案的意義：https://stackoverflow.com/a/890243/1317826

我無法理解如何從布爾表構建最佳的子集。

分區上的問題維基百科的文章有太：http://en.wikipedia.org/wiki/Partition_problem

是否有人可以擺脫一些關於它的光？

Answer 1

您需要的一切都在您發佈的答案中。首先，當您使用僞多項式時間算法創建表格時，您不會存儲布爾值值（如果可達，則爲True，否則爲False），但是添加到子集中的元素的值。比你應該能夠通過簡單地減去你獲得的總和來構建子集。

所以算法是：

1. 對於您所設定的每個數字x_i：

   1. 設置p(1, x_i) = x_i

   2. 對於所有其他領域p(row, sum)將它設置爲x_i如果p(row-1, sum-x_i) != 0

2. 所以現在p(row, sum) = x意味着我們可以利用我們一套一些row元素和它們的最後一個是x得到sum。

3. 一旦p(some_row, N/2) != 0你可以通過取其值x，並移動到p(some_row - 1, N/2 - x)等構造子集。

希望這說清楚。

順便說一句。有沒有辦法在答案中寫乳膠？