我有一个问题，它是 NP 完全的分区问题的变体。这是一个优化问题，而不是一个决策问题。
问题：将一个数字列表划分为两个子集，使它们的总和之差最小，然后找到这两个子集。如果n是偶数，那么大小应该是n/2，如果是奇数，那么floor[n/2]和ceil[n/2]。
假设伪多项式时间 DP 算法最适合精确解，如何修改它来解决这个问题？解决这个问题的最佳近似算法是什么？
问问题
261 次
1 回答
0
由于您没有指定使用哪种算法，我假设您使用此处定义的算法： http ://www.cs.cornell.edu/~wdtseng/icpc/notes/dp3.pdf
然后使用此算法添加一个变量来跟踪最佳结果，将其初始化为N（列表中所有数字的总和，因为您总是可以将一个子集作为空集）并且每次更新时T（例如：T[i ]=true) 你做类似的事情bestRes = abs(i-n/2)<bestRes : abs(i-n/2) : bestRes。而你返回bestRes。这当然不会改变算法的复杂性。
我不知道你的第二个问题。
于 2013-06-16T15:16:39.040 回答