将一组数字分为 k 个子集，使值均匀分布
Possible Duplicate:
equal k subsets algorithm
Say I've a set of numbers, I want to divide the numbers into k subsets such that the numbers are evenly distributed. By evenly distributed, I mean the sum of values in the subsets are closest to other sums of other subsets. Can we implement a DP solution to this problem??
Please suggest!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我所能提供的只是我最好的尝试，这里是：
在我看来，如果 m 是你的集合的大小，那么 m/k = n;这是每个集合中元素的数量。
现在我假设您正在使用整数，假设我们有一个集合， s:
s ={1,2,3,4,5,6,7,8}
现在这是一个简单的想法，如果您对集合进行排序，那么仓位总和
-Sum(0 和 last-0) = Sum(1,Last-1) = Sum(2,last-2) = Sum(3,last-3)... 等等。
变量为：
所以我们需要 4 组：
s1 = 1,8 = 总和为 9
s2 = 2,7 = 总和为 9
s3 = 3,6 = 总和为 9
s4 = 4,5 = Sum is 9
现在，如果集合大小是奇数和/或 k 是奇数，当然会出现一些棘手的情况，但这些可以使用特殊情况来处理 - 实现最适合您的特定情况的情况目的。
希望这能给你带来正确的推动，或者几乎任何方向的推动。
All I can offer is my best attempt, here goes:
It seems to me that if m is the size of your set, then m/k = n; which is the number of elements in each set.
Now I am assuming you are working with integers, lets say we a set, s:
s ={1,2,3,4,5,6,7,8}
Now this is a simple idea that if you set is sorted then the sum of positions
-Sum(0 and last-0) = Sum(1,Last-1) = Sum(2,last-2) = Sum(3,last-3)... and so forth.
the variables would be:
so we want 4 sets:
s1 = 1,8 = Sum is 9
s2 = 2,7 = Sum is 9
s3 = 3,6 = Sum is 9
s4 = 4,5 = Sum is 9
Now there will of course be some trickiness if the set size is odd and/or if k is odd, but these can be dealt with using special cases- implementing the situation that works best for your specific purpose.
Hope this gives you a push in the right, or pretty much any direction.