这是一个创建于 1574 天前的主题，其中的信息可能已经有所发展或是发生改变。
给定n个三维元组(a, b, c), 将这n个元组分成m组.
那么(a_i, b_i, c_i)是第 i 组的平均值.i∈[1,m]
于是我们就得到了m个三维元组(a_i, b_i, c_i)
我们想要的是这 m 个三位元组在每个维度上都尽可能地接近. 严谨的说法就是: 1/a'*Σ(a_i-a')^2+1/b'*Σ(b_i-b')^2+1/c'*Σ(c_i-c')^2 尽可能小. 其中(a',b',c')是这 m 个元组的平均值
这应该是背包问题的变形, 只能求近似解.
因为有多个维度, 就不太好用贪心算法. 想知道大家有什么思路,可以分享一下?
目前尚无回复
Select Language