如何找出集合中的哪些数字与另一个给定数字相加?

这就是 Subset Sum 问题,即 NP-Complete . 但这并不意味着没有找到子集和的算法。

这就是 Knapsack Problem 它是NP完全的。除了小的输入集之外,您不容易精确地解决它。对于任何大小合适的问题集,解决问题都是宇宙的一个生命周期。

也就是说,有遗传算法背包求解器。

正如上面的成员所说,这是子集和问题(或背包问题)。 然而,说它不能有效地完成并不十分精确。这是可以做到的,只是不能 在多项式时间。实际上,使用动态编程的解决方案非常简单 和递归(在伪多项式时间)。

给定整数[a_1,…,a_n]和数字t,

定义数组s[i,k]以表示元素之间是否存在子集 AA1,…一个i加上k(这是一个二进制矩阵)。

然后我们可以定义如下递归关系:

s[i,k]=s[i-1,k]或s[i-1,k-a_j]

换句话说,这意味着我们要么使用元素a_i,要么不使用元素a_i。 答案位于S[N,T]。

构造矩阵s的工作量是多少? 好吧,s有n*t元素。要计算每个元素, 我们必须工作。所以完整的运行 时间是O(n*t)。

现在看来,我已经证明了p=np,就像这样 似乎是一个多项式时间算法。但是,记住 我们用二进制来度量输入大小,所以对于一些 P.

我不认为有人会说上面的解决方案,当 实施得当是不合理的。事实上,对很多人来说 合理的问题尺寸,性能良好。

另外,有一些启发式方法可以解决这个问题,但是我是 不是那个领域的专家。

这是的版本 the knapsack problem . 它是NP完全的,所以你不会得到一个好的一般答案。你的交易量有多大?是像你展示的5,还是更像500?

好啊。很多人提到了这个问题的名称,并提到了它有多困难。一般来说,它们是正确的。但是,您有一个非常具体的案例需要解决。首先要问的问题是,你是否认为你的100笔交易接近于正确的交易。你有一些总数(“你的”总数)。他们有一些总数。(“实际”总计)。因此,您的一些交易是伪造的。如果你怀疑这里面只有几个伪造的交易,那么这就没那么糟糕了。例如,让我们考虑只有一个伪事务的情况。在这种情况下,我们只需要检查100个不同的数字。如果有2个伪造的反式,那么你会看到100*99的支票,而在4个伪造的反式上,事情会变得疯狂,几乎有100000000步。不过,如果你所做的只是添加一些int,那就不太可怕了。

另一种可能的快捷方式是检查数据的性质(顺便问一下,是否可以发布100个“数字”和预期的总和?)你的总数是多少?有没有这么大的值,去掉它们会使你的和突然低于实际的和?如果是这样,你知道这些价值观不能是假的。例如,在您的示例中,7是绝对必需的。

        bool bBreak = false;
        int iEnd = 13;
        ArrayList ar1 = new ArrayList();
        ar1.Add(2);
        ar1.Add(4);
        ar1.Add(5);
        ar1.Add(7);

        String s1 = " ";
        foreach (int i in ar1)
        {
            if (i == iEnd)
            {
                s1 = "Result = " + i;
                bBreak = true;
            }
            if (bBreak) break;
            ArrayList ar2 = new ArrayList();
            ar2.AddRange(ar1);
            ar2.Remove(i);
            foreach (int j in ar2)
            {
                if ((i + j) == iEnd)
                {
                    s1 = "Results = " + i + ", " + j;
                    bBreak = true;
                }

                if (bBreak) break;
                ArrayList ar3 = new ArrayList();
                ar3.AddRange(ar2);
                ar3.Remove(j);
                foreach (int k in ar3)
                {
                    if (bBreak) break;
                    if ((i + j + k) == iEnd)
                    {
                        s1 = "Results = " + i + ", " + j + ", " + k;
                        bBreak = true;
                    }
                }
            }
        }
        Console.WriteLine(s1);

是的,这是可能的。不确定此日志是否仍然打开。但您需要执行Excel解算器加载项。将所有数字贴在相邻单元格上,1。然后输入所需的输出编号。然后,所有使用的数字,将保持其相邻的“1”,而未使用的将变成“0”。然后做一个过滤公式,只列出那些旁边有“1”的。