计算数组的所有子集，其中最大数字是剩余数字的总和

Question

我一直在努力应对 Greplin 挑战的第 3 级。对于那些不熟悉的人来说，问题如下：

您必须找到数组的所有子集，其中最大数字是其余数字的总和。例如，对于输入：

（1、2、3、4、6）

子集是

1 + 2 = 3

1 + 3 = 4

2 + 4 = 6

1 + 2 + 3 = 6

这是您应该使用的号码列表 运行你的代码。密码是 子集的数量。在上述情况下 答案是 4。

3、4、9、14、15、19、28、37、47、50、54、56、59、61、70、73、78、81、92、95、97、99

I能够编写一个解决方案，构建 22 个数字的所有 400 万多个组合，然后对其进行测试所有这些都会给我正确的答案。问题是需要 40 多分钟才能完成。在网上搜索后，似乎有几个人能够编写一种算法，在不到一秒的时间内得到这个问题的答案。任何人都可以用伪代码解释比计算成本昂贵的暴力方法更好的方法来解决这个问题吗？这让我发疯！

Answer 1

诀窍在于您只需要记录做事的方法有多少种。由于数字已排序且为正数，因此这非常容易。这是一个有效的解决方案。 （在我的笔记本电脑上花费的时间不到 0.03 秒。）

#! /usr/bin/python

numbers = [
    3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56,
    59, 61, 70, 73, 78, 81, 92, 95, 97, 99]

max_number = max(numbers)
counts = {0: 1}
answer = 0
for number in numbers:
    if number in counts:
        answer += counts[number]
    prev = [(s,c) for (s, c) in counts.iteritems()]
    for (s, c) in prev:
        val = s+number;
        if max_number < val:
            continue
        if val not in counts:
            counts[val] = c
        else:
            counts[val] += c
print answer

Answer 2

我们知道这些值非零并且从左到右单调增长。

一个想法是枚举可能的总和（任何顺序，从左到右都可以）
然后枚举该值左侧的子集，
因为右边的值不可能参与（它们会使总和
太大了）。我们不必实例化该集合；正如我们所考虑的
每个值，看看如何影响总和。它可能太大（忽略
该值不能在集合中），正好（它是集合中的最后一个成员），
或太小，此时它可能会也可能不会在集合中。

【这个问题让我第一次玩Python。有趣。]

这是 Python 代码；根据 Cprofile.run 这需要 0.00772 秒
在我的 P8700 2.54Ghz 笔记本电脑上。

values = [3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99]

def count():
   # sort(values) # force strictly increasing order
   last_value=-1
   duplicates=0
   totalsets=0
   for sum_value in values: # enumerate sum values
      if last_value==sum_value: duplicates+=1
      last_value=sum_value
      totalsets+=ways_to_sum(sum_value,0) # faster, uses monotonicity of values
   return totalsets-len(values)+duplicates

def ways_to_sum(sum,member_index):
   value=values[member_index]
   if sum<value:
      return 0
   if sum>value:
      return ways_to_sum(sum-value,member_index+1)+ways_to_sum(sum,member_index+1)
   return 1

我得到的结果计数是 179。（与另一个海报的结果匹配。）

编辑：ways_to_sum 可以使用尾递归循环部分实现：

def ways_to_sum(sum,member_index):
   c=0
   while True:
      value=values[member_index]
      if sum<value: return c
      if sum==value: return c+1
      member_index+=1
      c+=ways_to_sum(sum-value,member_index)

这需要 0.005804 秒来运行：-}相同的答案。

Answer 3

运行时间不到 5 毫秒 (python)。它使用动态编程的一种变体，称为记忆递归。 go 函数计算前 p+1 元素的子集数量，其总和为 target。由于列表已排序，因此只需为每个元素（作为 target）调用一次函数并对结果求和即可：

startTime = datetime.now()
li = [3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99]
memo = {}
def go(p, target):
    if (p, target) not in memo:
        if p == 0:
            if target == li[0]:
                memo[(p,target)] = 1
            else:
                memo[(p,target)] = 0
        else:
            c = 0       
            if li[p] == target: c = 1
            elif li[p] < target: c = go(p-1,target-li[p])
            c += go(p-1, target)
            memo[(p,target)] = c
    return memo[(p,target)]

ans = 0
for p in range(1, len(li)):
    ans += go(p-1, li[p])

print(ans)
print(datetime.now()-startTime)

Answer 4

这是

public class A {

  static int[] a = {3,4,9,14,15,19,28,37,47,50,54,56,59,61,70,73,78,81,92,95,97,99};

  public static void main(String[] args) {
    List<Integer> b = new ArrayList<Integer>();

    int count = 0;
    for (int i = 0; i < a.length; i++) {
        System.out.println(b);
        for (Integer t:b) {
        if(a[i]==t)
        {
        System.out.println(a[i]);
            count++;
            }
        }

        int size = b.size();
        for (int j = 0; j < size; j++) {
        if(b.get(j) + a[i] <=99)
            b.add(b.get(j) + a[i]);
        }
            b.add(a[i]);
    }

    System.out.println(count);

  }
}

伪代码（带解释）：

1. 存储以下变量

   i.) 到目前为止子集的“计数”

   ii.) 包含所有可能子集之和的数组 b

   2.迭代数组（比如a）。对于每个元素 a[i]

   i.)遍历数组b并计算a[i]出现的次数。将其添加到“计数”

   ii.)遍历数组 b 并为每个元素 b[j].add (a[i]+b[j]) 到 b，因为这是一个可能的子集和。 （如果a[i]+b[j]> a中的最大元素，则可以忽略添加）

   iii.) 将 a[i] 添加到 b。

3.你有数:)

Answer 5

我使用了 Java 中的组合生成器类：

http://www.merriampark.com/comb.htm< /a>

迭代组合并查找有效子集花费了不到一秒的时间。 （我认为使用外部代码不符合挑战，但我也没有申请。）

Answer 6

public class Solution {

   public static void main(String arg[]) {
    int[] array = { 3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61,
        70, 73, 78, 81, 92, 95, 97, 99 };
    int N = array.length;
    System.out.println(N);
    int count = 0;
    for (int i = 1; i < 1 << N; i++) {
        int sum = 0;
        int max = 0;
        for (int j = 0; j < N; j++) {
        if (((i >> j) & 1) == 1) {
            sum += array[j];
            max = array[j];
        }
        }
        if (sum == 2 * max)
        count++;
    }
    System.out.println(count);
    }

    public static boolean isP(int N) {
    for (int i = 3; i <= (int) Math.sqrt(1.0 * N); i++) {
        if (N % i == 0) {
        System.out.println(i);
        // return false;
        }
    }
    return true;
    }
}

希望它有帮助，但不要只是复制和粘贴。

Answer 7

我不想死马当活马医，但这里发布的大多数解决方案都错过了优化的关键机会，因此执行时间延长了 6 倍。

与其迭代输入数组并搜索与每个值匹配的总和，不如只计算一次所有可能的相关总和，然后查看哪些总和出现在原始输入数组中，效率要高得多。 （“相关”总和是任何子集总和 <= 数组中的最大值。）

第二种方法的运行速度大约快 6 倍——通常是毫秒而不是厘秒——仅仅是因为它调用了大约 1 的递归求和函数/第六次！

这种方法的代码和完整的解释可以在这个 github 存储库中找到（它是用 PHP 编写的，因为这是给我这个挑战的人所要求的）：

https://github.com/misterrobinson/greplinsubsets