等k子集算法
有谁知道相等 k 子集算法的良好且有效的算法吗？最好是可以处理 100 个元素向量的 c 或 c++，可能具有复杂性和时间估计
。 9 元素向量
x = {2,4,5,6,8,9,11,13,14}
我需要生成所有 k=3 不相交子集，总和 = 24 该算法应该检查是否有 k 个不相交的子集，每个子集的元素总和为 24，并按升序列出它们（子集内和子集之间），或者查看解是否不存在
解决方案
解 1：{2 8 14} { 4 9 11} {5 6 13}
解决方案 2：{2 9 13} {4 6 14} {5 8 11}
谢谢
does anyone know a good and efficient algorithm for equal k subsets algorithm ? preferably c or c++ which could handle a 100 element vector maybe with a complexity and time estimation
ex. 9 element vector
x = {2,4,5,6,8,9,11,13,14}
i need to generate all k=3 disjoint subsets with sum = 24
the algorithm should check if there are k disjoint subsets each with sum of elements 24, and list them in ascending order(in subset and between subsets) or to see if the solution doesn't exists
Solutions
solution 1: {2 8 14} {4 9 11} {5 6 13}
solution 2: {2 9 13} {4 6 14} {5 8 11}
Thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
不幸的是，受限的 k 子集问题是一个难题 ...如果你想生成所有这样的k子集，你别无选择，只能评估许多可能的候选者。
您可以执行一些优化来减少搜索空间。
给定一个包含整数值的域
x，给定一个正整数目标 M，
给定子集的正整数 k 大小，
x候选值来减少搜索空间。当向量 x 包含负值时，许多优化（偶数/奇数排除除外）不再有用/有效。在这种情况下，您几乎必须进行详尽的搜索。正如 Jilles De Wit 指出的，如果 X 包含负数，您可以将 X 中最小值的绝对值添加到X 的每个成员。这会将所有值移回正范围 - 使我上面描述的一些优化再次成为可能。然而，这要求您能够在扩大的范围内准确地表示正值。实现此目的的一种方法是在内部使用更广泛的类型（例如 long 而不是 int）来执行子集选择搜索。但是，如果您这样做，请记住在返回结果时将结果子集按相同的偏移量缩小。
Unfortunately the constrained k-subset problem is a hard problem ... and if you want to generate all such k-subsets, you have no choice but to evaluate many possible candidates.
There are a couple of optimizations you can perform to reduce the search space.
Given a domain
xconstaining integer values,Given a positive integer target M,
Given a positive integer k size for the subset,
xthat could be part of the sum.Many of these optimizations (other than the even/odd exclusion) are no longer useful/valid when the vector x contains negative values. In this case, you pretty much have to do an exhaustive search.As Jilles De Wit points out, if X contains negative numbers you could add the absolute value of the smallest value in X to each member of X. This would shift all values back into positive range - making some of the optimizations I describe above possible again. This requires, however, that you are able to accurately represent positive values in the enlarged range. One way to achieve this would be to internally use a wider type (say long instead of int) to perform the subset selection search. If you do this, however, remember to scale the results subsets back down by this same offset when you return your results.