V2EX = way to explore
V2EX 是一个关于分享和探索的地方
Sign Up Now
For Existing Member Sign In
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
This topic created in 2069 days ago, the information mentioned may be changed or developed.
给定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 个元组的平均值
这应该是背包问题的变形, 只能求近似解.
因为有多个维度, 就不太好用贪心算法. 想知道大家有什么思路,可以分享一下?
No Comments Yet
Select Language