在使用动态规划伪多项式时间算法解决分区问题后,我需要找到最优子集。
更具体地说,我无法理解这个答案:https://stackoverflow.com/a/890243/1317826
我无法理解如何从 bool 表构造最佳子集。
关于分区问题的维基百科文章也有:http://en.wikipedia.org/wiki/Partition_problem
有人可以解释一下吗?
最佳答案
您所需要的一切都在您发布的答案中。
首先,当您使用伪多项式时间算法创建表时,您不会存储 bool 值 值(如果可达则为 True,否则为 False),而是您添加到的元素的值子集。你应该能够通过简单地从你获得的总和中减去它来构造子集。
所以算法是:
对于集合中的每个数字
x_i
:设置
p(1, x_i) = x_i
对于所有其他字段
p(row, sum)
将其设置为x_i
ifp(row-1, sum-x_i) != 0
所以现在
p(row, sum) = x
意味着我们可以通过获取我们的一些row
元素来获得sum
设置,其中最后一个是x
。一旦
p(some_row, N/2) != 0
您可以通过获取它的值x
并移动到p 来构建子集(some_row - 1, N/2 - x)
等等。
希望这能说明问题。
顺便说一句。有没有办法在答案中写 latex ?
关于algorithm - PartitionProblem - 找到最优子集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17189125/