质点分组

kastin · 发表于 2013-12-7 13:09:05

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

有n种不同质量的质点（质量不一定为整数），将其划分为彼此重量平衡的两组的划分方式共有N种。问N的最大值是多少？

这一题在数学领域有着极其重要的作用，在分析学、集合论、数论里面都有它的等价形式的命题。

wayne · 发表于 2013-12-7 13:15:37

彼此重量平衡该怎么理解

kastin · 发表于 2013-12-7 13:25:51

wayne 发表于 2013-12-7 13:15
彼此重量平衡该怎么理解

就是分成两组，放在天平两端能够平衡。

zhouguang · 发表于 2013-12-9 12:56:51

貌似即使问N是否为0，也是NP问题。

kastin · 发表于 2013-12-9 14:14:53

本帖最后由 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

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 质点分组

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

点评

评分