algorithm - 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_iifp(row-1, sum-x_i) != 0

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

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

希望这可以说清楚。

顺便提一句。有没有办法在答案中写乳胶？