怎么分玻璃球?

APC
阿司匹林 2011-01-01 字数 105

M*N个玻璃球,每个玻璃球的轻重不一,要分成N个组,每组M个,

要怎么分才能使最重的一组和最轻的一组重量差最小?

Algorithm 算法
6 个回复
wqddmh
无穷大的马猴|少爷们师爷,马三少爷 2011-01-01

还挺难的。。。

先求和,求均值,然后往上凑?

是不是还要排下序?

【 在 APC (阿司匹林) 的大作中提到: 】

: M*N个玻璃球,每个玻璃球的轻重不一,要分成N个组,每组M个,

: 要怎么分才能使最重的一组和最轻的一组重量差最小?

APC
阿司匹林 2011-01-03

我就想到全组合,可是随着M*N增加的太快几乎就不可行。

这个问题还有一问,是每一组和平均值差的绝对值之和最小。

我连第一问都没想好怎么做,不知道这问题的原型是哪里来的。

【 在 wqddmh (无穷大的马猴|少爷们师爷,马三少爷) 的大作中提到: 】

: 还挺难的。。。

: 先求和,求均值,然后往上凑?

: 是不是还要排下序?

: ...................

wxstorm
企鹅 2011-01-03

subset吧

这个已经NP了

【 在 APC (阿司匹林) 的大作中提到: 】

: 我就想到全组合,可是随着M*N增加的太快几乎就不可行。

: 这个问题还有一问,是每一组和平均值差的绝对值之和最小。

: 我连第一问都没想好怎么做,不知道这问题的原型是哪里来的。

: ...................

wqddmh
无穷大的马猴|少爷们师爷,马三少爷 2011-01-04

如果第二问不需要满足第一问的要求的话,那么第二问就是个聚类问题。

固定类数,固定类成员数量。恩,是吧?

【 在 APC (阿司匹林) 的大作中提到: 】

: 我就想到全组合,可是随着M*N增加的太快几乎就不可行。

: 这个问题还有一问,是每一组和平均值差的绝对值之和最小。

: 我连第一问都没想好怎么做,不知道这问题的原型是哪里来的。

: ...................

APC
阿司匹林 2011-01-05

真这么麻烦?这个问题已经困扰我好长一段时间了,以至于我想把以前看过的数学书重学一遍。

【 在 wxstorm (企鹅) 的大作中提到: 】

: subset吧

: 这个已经NP了

APC
阿司匹林 2011-01-05

应该是要满足的。

但是如果不需要满足第一问的情况按聚类问题来处理,也并没有让问题得到简化啊。

问题只是转化成一维空间的N个点与中心点距离和最小,可怎么由M*N个点聚成N个点

以及判断,这个算法的复杂度和全组合好像也是同阶的。

【 在 wqddmh (无穷大的马猴|少爷们师爷,马三少爷) 的大作中提到: 】

: 如果第二问不需要满足第一问的要求的话,那么第二问就是个聚类问题。

: 固定类数,固定类成员数量。恩,是吧?