6

我一直在努力应对 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

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

4

7 回答 7

6

诀窍是你只需要记录有多少种方法可以做事。由于数字已排序且为正数，因此这很容易。这是一个有效的解决方案。（在我的笔记本电脑上需要不到 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
于 2011-06-15T06:44:26.187 回答
3

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

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

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

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

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 秒才能运行 :-} 相同的答案。

于 2011-06-15T05:24:29.327 回答
2

这运行时间不到 5 毫秒（python）。它使用一种称为记忆递归的动态编程变体。该go函数计算了第一个p+1元素的子集数，总和为target. 因为列表是排序的，所以对每个元素（as）调用一次函数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)
于 2011-06-15T06:43:27.980 回答
1

这有效

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.你有数:)

于 2012-09-12T19:41:57.713 回答
0

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

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

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

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

https://github.com/misterrobinson/greplinsubsets

于 2014-09-30T01:12:29.473 回答
0

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

http://www.merriampark.com/comb.htm

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

于 2011-06-15T05:09:01.760 回答
0 
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;
    }
}

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

于 2012-10-09T21:19:25.850 回答