等于K个子集算法 [英] equal k subsets algorithm

问题描述

没有人知道一个良好的，高效的算法等于K个子集的算法？ preferably C或C ++这可能与复杂性和时间的估计可能处理100件载体

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

恩。 9元素矢量

X = {2,4,5,6,8,9,11,13,14}

x = {2,4,5,6,8,9,11,13,14}

我需要生成所有的k = 3不相交的子集的额= 24 算法应检查是否存在与元件24的数的k不相交的子集的每个，并列出它们以升序（在子集，子集之间），或以查看是否解决方案不存在

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

解决方案

解决方案1：{2 8 14} {4 9 11} {5 6 13}

solution 1: {2 8 14} {4 9 11} {5 6 13}

解决方案2：{2 9 13} {4 6 14} {5 8 11}

solution 2: {2 9 13} {4 6 14} {5 8 11}

感谢

推荐答案

不幸的是，受限的 K-子问题是一个很难的问题 ......如果你想生成的所有这样的K-子集，你有没有只好评估多种可能的候选人的。

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.

由于域 X constaining整数值， 给定一个正整数目标男， 给定一个正整数k大小为子集，

Given a domain x constaining integer values, Given a positive integer target M, Given a positive integer k size for the subset,

1. 当x只包含正整数，并给予上限男，从x大于或等于M.较大，这些不可能是子集的一部分删除所有项目。
2. 同样，对于含正整数K> 1，给定M和X，删除从x的所有项目这比M + min0 +分1 ......貂较大。从本质上讲，删除所有在超过M的总和选择小值，他们会的结果，因为即使它不可能是子集的一部分的大的值。
3. 您也可以使用奇/偶斥原理，大肆削减你的搜索空间。例如，对k为奇数，M为偶数，你知道的总和要么包含三个偶数或两个奇一偶数。您可以使用此信息从消除候选值x 这可能是总和的一部分，以减少搜索空间。
4. 排序向量x - 这可以让你快速排除不可能包含在总和值

1. When x only contains positive integers, and given a upper bound M, remove all items from x larger than or equal to M. These can't possibly be part of the subset.
2. Similarly, for k > 1, a given M, and x containing positive integers, remove all items from x which are larger than M + min0 + min1 ... minK. Essentially, remove all of the large values which can't possibly be part of the subset since even when selecting small values they will results in a sum in excess of M.
3. You can also use the even/odd exclusion principle to pare down your search space. For instance, of k is odd and M is even, you know that the sum will either contain three even numbers or two odd and one even. You can use this information to reduce the search space by eliminating candidate values from x that could be part of the sum.
4. Sort the vector x - this allows you to rapidly exclude values that can't possibly be included in the sum.

<打击>许多优化（比偶/奇排除其他）都不再有用/有效时，向量x包含负值。在这种情况下，pretty的很多都做了详尽的搜索。

作为Jilles德维特指出的，如果X包含负数，你可以在X-加上最少值的绝对值X的每个成员这所有的值转向回正数范围 - 做一些我上面描述可能再次优化。然而，这需要，你能够准确地重新present正值在放大范围内。实现这将是单程内部使用更宽的类型（例如，而不是长整型）执行子集选择的搜索。如果你这样做，但是，请记住缩放结果子集回落此相同的偏移，当你返回你的结果。

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.

这篇关于等于K个子集算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！