algorithm - PartitionProblem - 找到最优子集

Question

在使用动态规划伪多项式时间算法解决分区问题后，我需要找到最优子集。

更具体地说，我无法理解这个答案:https://stackoverflow.com/a/890243/1317826

我无法理解如何从 bool 表构造最佳子集。

关于分区问题的维基百科文章也有:http://en.wikipedia.org/wiki/Partition_problem

有人可以解释一下吗？

Answer 1

您所需要的一切都在您发布的答案中。

首先，当您使用伪多项式时间算法创建表时，您不会存储 bool 值 值(如果可达则为 True，否则为 False)，而是您添加到的元素的值子集。你应该能够通过简单地从你获得的总和中减去它来构造子集。

所以算法是:

1. 对于集合中的每个数字 x_i:

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

   2. 对于所有其他字段 p(row, sum) 将其设置为 x_i if p(row-1, sum-x_i) != 0

2. 所以现在 p(row, sum) = x 意味着我们可以通过获取我们的一些 row 元素来获得 sum设置，其中最后一个是 x。

3. 一旦 p(some_row, N/2) != 0 您可以通过获取它的值 x 并移动到 p 来构建子集(some_row - 1, N/2 - x) 等等。

希望这能说明问题。

顺便说一句。有没有办法在答案中写 latex ？