无法从集合中获得的最小和

Question

给定一组正整数，其元素不必不同，我需要找到从给定集合的任何子集都不能得到的最小非负和。

例如：如果S={1，1，3，7}，我们可以得到0作为（S={}），1作为（S={1}），2作为（S={1，1}），3，4作为（S“={1，3}），5作为（S“={1，1，3}），但我们无法得到6。

现在我们得到一个数组A，由N个正整数组成。它们是M个查询，每个查询由两个整数组成，分别描述i't查询：我们需要找到无法从数组元素{A[Li]，A[Li 1]，…，A[Ri-1]，A[Ri]}中获得的和。

我知道用蛮力方法找到它要在O（2^n）中完成。但是给定1≤N，M≤100,000。这是做不到的。他们的任何有效方法也是如此。

Answer 1

这是子集和问题的一种变体，它是NP完全的，但这里可以采用基于递归公式的伪多项式动态规划解决方案：

f(S,i) = f(S-arr[i],i-1) OR f(S,i-1)
f(-n,i) = false
f(_,-n) = false
f(0,i) = true

递归公式基本上是一个详尽的搜索，如果您可以使用元素i或在没有元素i的情况下获得它，则可以实现每个求和。

动态规划是通过构建一个SUM 1 x n 1表（其中SUM是所有元素的总和，n是元素的数量）并自下而上构建来实现的。

像这样的东西：

table <- SUM+1 x n+1 table
//init:
for each i from 0 to SUM+1:
    table[0][i] = true
for each j from 1 to n:
    table[j][0] = false
//fill the table:
for each i from 1 to SUM+1:
    for each j from 1 to n+1:
         if i < arr[j]:
              table[i][j] = table[i][j-1]
         else:
              table[i][j] = table[i-arr[j]][j-1] OR table[i][j-1]

一旦你有了表，你需要最小的i，这样对于所有j：table[i][j]=false

解决方案的复杂性为O（n*SUM），其中SUM是所有元素的总和，但请注意，在找到所需的数字后，实际上可以修剪算法，而无需继续下一行，这是解决方案不需要的。

Answer 2

假设我们有一个bool数组，表示迄今为止尚未找到的数字（通过求和的方式）。

对于我们在S的有序（递增值）子集中遇到的每个数字，我们执行以下操作：

1. 对于编号中位置i处的每个现有值，我们将编号设置为真

使用这种筛选，我们会将所有找到的数字标记为True，当算法完成时，遍历数组会找到最小的不可求和。

显然，我们不能有这样的解决方案，因为数组必须是无限的，才能处理所有的数集。

这个概念可以通过做一些观察来改进。输入1,1,3，数组变成（按顺序）：

可以提出一个重要的意见：

• （3） 对于下一个数字，如果已经找到之前的数字，则会将其添加到所有这些数字中。这意味着，如果在数字之前没有间隙，则在处理该数字之后将没有间隙

对于7的下一个输入，我们可以断言：

• （4）由于输入集是有序的，因此不会有小于7
的数字
• （5）如果没有小于7的数字，则无法获得6

我们可以得出以下结论：

• （6） 第一个缺口表示无法达到的最小数量

由于（3）和（6），我们实际上不需要数字数组，我们只需要一个值，即max来表示迄今为止找到的最大数字。

这样，如果下一个数字n大于max 1，则会产生一个间隙，而max 1是最小的无法获得的数字。

否则，max变为max n。如果我们遍历了整个代码，结果是最大值1。

实际代码（C#，易于转换为C）：

static int Calculate(int[] S)
{
    int max = 0;
    for (int i = 0; i < S.Length; i++)
    {
        if (S[i] <= max + 1)
            max = max + S[i];
        else
            return max + 1;
    }
    return max + 1;
}

应该运行得很快，因为它显然是线性时间（O（n））。由于应该对函数的输入进行排序，使用快速排序时，这将变为O（nlogn）。我在不到5分钟的时间内，在8个内核上获得了结果，M=N=100000。

如果数字上限为10^9，则可以使用基数排序来近似O（n）时间进行排序，但是由于需要大量的排序，这仍然会超过2秒。

但是，我们可以在排序之前使用随机1的统计概率来消除子集。开始时，检查S中是否存在1，如果不存在，则每个查询的结果都是1，因为无法获取。

从统计学上讲，如果我们从10^9个数字中随机抽取10^5次，我们有99.9%的几率得不到一个1。

在每次排序之前，检查该子集是否包含1，如果不包含1，则其结果为1。

通过此修改，代码在我的机器上运行只需2毫秒。这是http://pastebin.com/rF6VddTx上的代码