给定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 个元组的平均值

这应该是背包问题的变形, 只能求近似解.

因为有多个维度, 就不太好用贪心算法. 想知道大家有什么思路,可以分享一下?

大佬有話說 (0)