计数总和大于或等于k的子集的数量

给定具有n个元素的数组，需要计数总和大于或等于k的子集的数量。计数总和大于或等于k的子集的数量

例如ARR [] = {1,5,9,2,3}，K = 16

1 + 5 + 9 + 2 = 17

1 + 5 + 9 + 3 = 18

1 + 5 + 9 + 2 + 3 = 20

5 + 9 + 2 = 16

5 + 9 + 3 = 17

5 + 9 + 2 + 3 = 19

答案是6.

我知道的一种方法是使用位掩码动态编程，并检查sum> = k并增加计数。这种方法的问题是N应该非常小，因为位掩码涉及指数运行时间。

上述问题是否还有其他有效算法？

在此先感谢。

来源

2017-07-26 Chandan

的元素都是积极的？ – Henry

它可以是两者的组合。但为了简单起见，我们只考虑积极因素 – Chandan

@亨利让我们考虑只有积极因素 – Chandan

，并使阵列Counts[Sum+1]其中总和为所有元素
设置Counts[0] = 1，其他元素的总和 - 零
对于以往x=arr[i]扫描从最终计数阵列，并增加这些条目，这可以从现有迄今数额和x组成

if Counts[j - arr[i]] > 0 then //this check might be omitted 
    Counts[j] = Counts[j - arr[i]] + Counts[j]

然后总结非零计数条目j>=k

复杂性是O(Sum * N)

如果可能的和的范围很大，但可能的和的数量不那么高（如arr=[1, 2, 3, 100000000, 100000001]阵列），则可以利用记忆化方法，并仅存储真正现有的变体在图

实施例：

arr=[1,2,3,5] 
Counts = [1,0,0,0,0,0,0,0,0,0,0,0] 
after arr[0]=1 
Counts = [1,1,0,0,0,0,0,0,0,0,0,0] 
after arr[1]=2 
Counts = [1,1,1,1,0,0,0,0,0,0,0,0] 
after arr[2]=3 
Counts = [1,1,1,2,1,1,1,0,0,0,0,0] 
after arr[3]=5 
Counts = [1,1,1,2,1,2,2,1,2,1,1,1] 

Counts[8] could be composed from 5 and existing Counts[3] with two variants 
1+2+5; 3+5

来源

2017-07-26 06:27:51 MBo

@亨利感谢您纠正 – MBo

如果k和元素值很小，这种方法也可以工作。如果arr中的每个元素都很大，说10^9会怎么样。所以所有元素的总和将是n * 10^9。如果我们遍历整个范围，程序将永远运行。 – Chandan

@Chandan你没有给出问题中的范围信息。我添加了关于memoization的注释。 – MBo

一种方法是使用递归创建子集并在从原始集合中省略的元素总和大于总数k时停止递归，其中total是数组所有元素的总和。

这里的说明方法的Java代码：

import java.util.ArrayList; 
import java.util.BitSet; 
import java.util.List; 

public class SubSet 
{ 

    public static void main(String[] args) 
    { 
     Integer[] set = { 1, 5, 9, 2, 3 }; 
     List<List<Integer>> subsets = subsetsK(set, 16); 
     for (List<Integer> subset : subsets) 
     { 
      System.out.println(subset); 
     } 
    } 

    static List<List<Integer>> subsetsK(Integer[] arr, int k) 
    { 
     int t = 0; 
     for (int n : arr) t += n; 

     List<List<Integer>> subsets = new ArrayList<>(); 
     allSubsets(subsets, arr, new BitSet(arr.length), 0, 0, t - k); 
     return subsets; 
    } 

    public static void allSubsets(List<List<Integer>> subsets, Integer[] arr, BitSet off, int pos, int sum, int lim) 
    { 
     if(sum > lim) return; 

     if(pos == arr.length) 
     { 
      subsets.add(toSubset(arr, off)); 
      return; 
     } 

     off.set(pos); 
     allSubsets(subsets, arr, off, pos + 1, sum + arr[pos], lim); 

     off.clear(pos); 
     allSubsets(subsets, arr, off, pos + 1, sum, lim); 
    } 

    static List<Integer> toSubset(Integer[] arr, BitSet off) 
    { 
     List<Integer> ss = new ArrayList<>(); 
     for (int i = 0; i < arr.length; i++) 
     { 
      if (!off.get(i)) 
       ss.add(arr[i]); 
     } 
     return ss; 
    } 
}

输出：

[5, 9, 3] 
[5, 9, 2] 
[5, 9, 2, 3] 
[1, 5, 9, 3] 
[1, 5, 9, 2] 
[1, 5, 9, 2, 3]

您可以运行/在这里编辑代码：Ideone

来源

2017-07-26 07:39:00 SirRaffleBuffle

计数总和大于或等于k的子集的数量

回答

相关问题