检查是否有一个数组的大小为 k 的子集具有 n 的和倍数

Question

晚上好，我在 java 中有一个数组，其中包含 n 个整数。我想检查是否有满足条件的条目的大小为 k 的子集：

这些 k 个条目的总和是 m 的倍数。

我怎样才能尽可能高效地做到这一点？我需要检查 n!/k!(n-k)! 个子集。

Answer 1

你可以使用动态规划。状态是（前缀长度，求和模 m，子集中的元素数）。转换很明显：我们要么再添加一个数字（增加子集中的元素数量并计算新的求和模 m），要么只增加前缀长度（不添加当前数字）。如果你只需要一个 yes/no 答案，你可以只存储最后一层值并应用位优化来更快地计算转换。时间复杂度为 O(n * m * k)，或大约 n * m * k / 64 位优化操作。 space 复杂度为 O(m * k)。对于几千个元素，它看起来是可行的。通过位优化，我的意思是使用像 C++ 中的 bitset 这样的东西，它可以使用按位运算同时对一组位执行操作。

Answer 2

我不喜欢这个解决方案，但它可能适合您的需要

public boolean containsSubset( int[] a , int currentIndex, int currentSum, int depth, int divsor, int maxDepth){

    //you could make a, maxDepth, and divisor static as well


    //If maxDepthis equal to depth, then our subset has k elements, in addition the sum of
    //elements must be divisible by out divsor, m
    //If this condition is satisafied, then there exists a subset of size k whose sum is divisible by m
    if(depth==maxDepth&&currentSum%divsor==0) 
         return true;

    //If the depth is greater than or equal maxDepth, our subset has more than k elements, thus
    //adding more elements can not satisfy the necessary conditions
    //additionally we know that if it contains k elements and is divisible by m, it would've satisafied the above condition. 
    if(depth>=maxdepth)
         return false;


    //boolean to be returned, initialized to false because we have not found any sets yet
    boolean ret = false;

    //iterate through all remaining elements of our array 
    for (int i = currentIndex+1; i < a.length; i++){
    //this may be an optimization or this line
    //for (int i = currentIndex+1; i < a.length-maxDepth+depth; i++){



         //by recursing, we add a[i] to our set we then use an or operation on all our subsets that could 
         //be constructed from the numbers we have so far so that if any of them satisfy our condition (return true) 
         //then the value of the variable ret will be true
         ret |= containsSubset(a,i,currentSum+a[i],depth+1,divisor, maxDepth);

    } //end for


    //return the variable storing whether any sets of numbers that could be constructed from the numbers so far.
    return ret;

}

然后调用这个方法

 //this invokes our method with "no numbers added to our subset so far" so it will try adding 
 // all combinations of other elements to determine if the condition is satisfied.
 boolean answer = containsSubset(myArray,-1,0,0,m,k);

编辑：

~~您可以通过对所有内容取模 (%) m 并删除重复项来优化它。对于 n and/or k 值较大但 m 值较小的示例，这可能是一个相当大的优化。~~

编辑 2：

我列出的上述优化没有帮助。您可能需要重复才能获得正确的信息。我的错。

编码愉快！如果您有任何问题，请告诉我！

Answer 3

如果数字有下限和上限，最好：

迭代 n 的所有 multiple，其中 lower_bound * k < multiple < upper_bound * k
使用动态编程检查数组中是否存在总和为 multiple 的子集（参见 Subset Sum problem）。

复杂度为 O(k^2 * (lower_bound + upper_bound)^2)。这种方法可以进一步优化，我相信仔细考虑。

否则你可以找到大小为 k 的所有子集。复杂度为 O(n!)。使用回溯（伪代码）：

function find_subsets(array, k, index, current_subset):
  if current_subset.size = k:
    add current_subset to your solutions list
    return

  if index = array.size:
    return

  number := array[index]
  add number to current_subset
  find_subsets(array, k, index + 1, current_subset)
  remove number from current_subset
  find_subsets(array, k, index + 1, current_subset)

检查是否有一个数组的大小为 k 的子集具有 n 的和倍数

Checking whether there is a subset of size k of an array which has a sum multiple of n

java

arrays

algorithm