给定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 个元组的平均值
这应该是背包问题的变形, 只能求近似解.
因为有多个维度, 就不太好用贪心算法. 想知道大家有什么思路,可以分享一下?
这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。
V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。
V2EX is a community of developers, designers and creative people.