质点分组
有n种不同质量的质点（质量不一定为整数），将其划分为彼此重量平衡的两组的划分方式共有N种。问N的最大值是多少？这一题在数学领域有着极其重要的作用，在分析学、集合论、数论里面都有它的等价形式的命题。 彼此重量平衡 该怎么理解 wayne 发表于 2013-12-7 13:15
彼此重量平衡 该怎么理解
就是分成两组，放在天平两端能够平衡。 貌似即使问N是否为0，也是NP问题。 本帖最后由 kastin 于 2013-12-9 17:51 编辑
zhouguang 发表于 2013-12-9 12:56
貌似即使问N是否为0，也是NP问题。
这个还不知道，但是可以肯定是一个比较难的问题。与之类似的还有一个子集的问题sum(ai*ci)=s, ai取1或者-1，s给定。求解的个数。这是个NP问题，目前数论界在研究，给出了一些特殊情况上下界的研究。
论文：Improved low-density subset sum algorithms
链接：http://www.dtc.umn.edu/~odlyzko/doc/arch/better.low.density.pdf
页:
[1]