3

我有一个像这样的集合S[00 01 10 11]和一个元素E作为11。我想找出这个集合的子集的数量，其数字总和大于或等于元素E的数字总和。

例如，在这种情况下，答案是 10。满足约束的 10 个集合是：

00 01 10 11 // Sum is 3 which is greater than 2 (sum of digits of E)
00 01 11 
00 10 11
01 10 11
00 11
01 11
10 11
11
00 01 10
01 10

上述子集的所有位数之和大于或等于 2（E的位数之和）。

我尝试了以下

public static void main(String[] args) {
    Set<String> inputSet = new HashSet<String>();
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();// specifies the length of the digts in the set.
    for (long i = 0 ; i < N; i++) {
        inputSet.add(sc.next());
    }
    long sum = 0;
    String E = sc.next();//
    sc.close();
    for (String str : E.split("(?!^)")) {
        sum = sum + Integer.parseInt(str);
    }
    List<Set<String>> subSets = new ArrayList<Set<String>>();
    for (String addToSets : inputSet) {
        List<Set<String>> newSets = new ArrayList<Set<String>>();
        for (Set<String> curSet : subSets) {
            Set<String> copyPlusNew = new HashSet<String>();
            copyPlusNew.addAll(curSet);
            copyPlusNew.add(addToSets);
            newSets.add(copyPlusNew);
        }
        Set<String> newValSet = new HashSet<String>();
        newValSet.add(addToSets);
        newSets.add(newValSet);
        subSets.addAll(newSets);
    }
    long sum1;
    long count = 0;
    for (Set<String> set : subSets) {
        sum1 = 0;
        for (String setEntry : set) {
            for (String s : setEntry.split("(?!^)")){
                sum1 = sum1 + Integer.parseInt(s);
            }
        }
        if (sum == sum1 || sum1 > sum)
            count = count+1;
    }
    System.out.println(count);
}

约束 1 <= N <= 10^5


1 <= M <= 20

上述方法不适用于 10 5范围内的集合大小。请帮助为此提供一种有效的方法。谢谢！

4

1 回答 1

2

解决这个问题的关键就是记住这一点addition is associative。所以当你添加这些数字时并不重要。因此，如果我们将其简化为已知问题，则很容易解决。

将您的输入数组转换为sum of digits array. 也就是说，如果您的原始数组是 A，那么与结果数组 B 的关系将是：

          B[i] = sum of digits of(A[i]).

说 K 是sum of digits(E)

然后你的问题减少到

     Find number of subsets in B whose sum is <= K

这很容易。

编辑： 

  public static void main(String[] args) {
    int[] A ={01,11,111};
    int B[] = new int[A.length];
    for(int i=0;i<A.length;i++){
        B[i]=getDigitSum(A[i]);
    }
     int E = 11;
    int K= getDigitSum(E);
    int N =B.length;
    Arrays.sort(B);
    int DP[][] = new int[B.length][B[B.length-1]+1];


    for (int i=0;i<N;i++) {
        DP[i][B[i]] = 1;

        if (i == 0) continue;

        for (int k=0;k<K;k++) {
            DP[i][k] += DP[i - 1][k];
        }
        for (int k=0;k<K;k++) {
            if( k + B[i] >= K) break ;
            DP[i][k + B[i]] += DP[i - 1][k];
        }
    }
    int sum=0;
    for(int i=0;i<K;i++) {
        sum = sum +DP[N-1][i];
    }
    int result = ((int)Math.pow(2,N)) - sum-1;
    System.out.println(result);

}

private static int getDigitSum(int num) {
    int sum =0;
    while(num >0){
       sum=sum+ (num%10);
        num= num/10;
    }
    return sum;
}
于 2015-07-09T19:31:12.723 回答