找到不能表示为 1,2 或序列中其他数字之和的最小可能数

Question

我是 C++ 的新手，在以下任务中需要逻辑帮助。

给定一个由n个正整数组成的序列（n < 10^6；每个给定的整数都小于10^6），编写一个程序，找出最小的正整数，不能表示为1、2或更多项的和给定序列的（即每个项目可以被取 0 或 1 次）。例子：输入：2 3 4，输出：1；输入：1 2 6，输出：4

我似乎无法从中构建逻辑，为什么最后一个输出是 4 以及如何在 C++ 中实现它，非常感谢任何帮助。到目前为止，这是我的代码：

    #include<iostream>
    using namespace std;

    const int SIZE = 3;

    int main()
    {
//Lowest integer by default
int IntLowest = 1;
int x = 0;
//Our sequence numbers
int seq;
int sum = 0;
int buffer[SIZE];
//Loop through array inputting sequence numbers
for (int i = 0; i < SIZE; i++)
{
    cout << "Input sequence number: ";
    cin >> seq;
    buffer[i] = seq;
    sum += buffer[i];
}
int UpperBound = sum + 1;

int a = buffer[x] + buffer[x + 1];
int b = buffer[x] + buffer[x + 2];
int c = buffer[x + 1] + buffer[x + 2];
int d = buffer[x] + buffer[x + 1] + buffer[x + 2];


for (int y = IntLowest - 1; y < UpperBound; y++)
{
    //How should I proceed from here?

}
return 0;
    }

Answer 1

Voreno 的答案实际上是解决 0-1 背包问题（http://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_Knapsack_Problem）。如果您点击链接，您可以阅读如何在不构建初始集的所有子集的情况下完成它（它们太多了，2^n）。如果约束小一点，比如 10^3，它会起作用。

但是当 n = 10^6 时，它仍然需要太多的时间和空间。但是没有必要解决背包问题——我们只需要找到我们无法得到的第一个数字。

更好的解决方案是对数字进行排序，然后遍历它们一次，为数组的每个前缀找到一个数字 x，这样您就可以使用该前缀获得区间 [1..x] 中的所有数字。此时我们无法得到的最小数是 x + 1。当您考虑下一个数 a[i] 时，您有两个选择：

1. a[i] <= x + 1，那么你可以得到所有数到 x + a[i]，
2. a[i] > x + 1，那么你不能得到 x + 1 并且你有你的答案。

例子：

给你数字 1、4、12、2、3。

您对它们进行排序（并得到 1、2、3、4、12），从 x = 0 开始，考虑每个元素并按以下方式更新 x：

1 <= x + 1，所以 x = 0 + 1 = 1。

2 <= x + 1，所以 x = 1 + 2 = 3。

3 <= x + 1，所以 x = 3 + 3 = 6。

4 <= x + 1，所以 x = 6 + 4 = 10。

12 > x + 1，所以我们找到了答案，它是 x + 1 = 11。

（编辑：修复了一个错误，添加了示例。）