8

这是我似乎在使用会计系统时遇到的一个问题。

我有一组交易，但它们的总和不等于会计部门认为应该的金额。他们不是在质疑数学，只是在质疑交易：p

是否有一种算法可以帮助我确定不应该包含集合中的哪些交易以使总和与给定金额匹配。

Given Set:  
2  
4  
5  
7

Given Sum Amount:
13

Result Set:
2
4
7

编辑： 集合中的事务少于 100 个。有没有人有一个 C# 示例，因为在 XKCD 问题中解决 NP 完全问题没有一个？

伙计，我应该获得CS学位。

4

7 回答 7

8

这是子集和问题，即NP-Complete。但这并不意味着没有找到子集总和的算法。

于 2009-07-29T19:43:45.443 回答
7

这是背包问题，它是NP完全的。除了小的输入集之外，你不会轻易地用任何东西来准确地解决它。对于任何体面大小的问题集，它都是需要解决的宇宙终生问题之一。

也就是说，那里有遗传算法背包求解器。

于 2009-07-29T19:40:09.337 回答
6

正如上面的成员所说，这是子集和问题（或背包问题）。但是，说它不能有效地完成并不是很准确。它可以完成，只是不是在多项式时间内。使用动态编程和递归（以及在伪多项式时间内），该解决方案实际上非常简单。

给定整数 [a_1, ... ,a_n] 和一个数 T，

定义数组 S[i,k] 以表示在 a_1, ... a_i 之间是否存在元素的子集，它们的总和为 k。（这是一个二进制矩阵）。

然后我们可以定义一个递归关系如下：

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

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

构造矩阵 S 的工作量是多少？好吧，S 有 n*T 个元素。要计算每个元素，我们必须做 O(1) 的工作。所以完整的运行时间是O(n*T)。

现在，似乎我已经证明了 P=NP，因为这似乎是一个多项式时间算法。但是，请记住，我们以二进制测量输入大小，因此对于某些 p，T = 2^p。

我认为没有人会说上述解决方案如果实施得当是不合理的。事实上，对于许多合理的问题规模，它的表现令人钦佩。

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

于 2009-07-29T20:07:34.840 回答
3

好的。很多人都给出了问题的名称，并提到了 NP 有多难。总的来说，它们是正确的。但是，您有一个非常具体的案例需要解决。要问的第一个问题是您是否认为您的 100 笔交易接近正确。你有一些总数（“你的”总数）。他们有一些总数。（“真实”总数）。因此，您的一些交易是虚假的。如果您怀疑那里只有少数虚假交易，那么这还不错。例如，让我们考虑只有一个虚假交易的情况。在这种情况下，我们只需要检查 100 个不同的数字。如果有 2 个伪造的反式，那么您正在查看 100*99 的支票，而 4 个伪造的反式将变得疯狂，几乎有 100,000,000 步。虽然如果你都是'

另一个可能的捷径是检查数据的性质（顺便说一句，是否可以发布 100 个“数字”和预期的总和？）。你的总和比实际总和高多少？是否有任何值如此之大以至于消除它们会使您的总和突然低于实际总和？如果是这样，您就知道这些值不可能是虚假的。例如，在您的示例中，绝对需要 7。

于 2009-07-29T21:45:12.407 回答
3

这是背包问题的一个版本。它是 NP 完全的，所以你不会得到一个好的一般答案。你的交易集有多大？是像你展示的那样是 5，还是更像是 500？

于 2009-07-29T19:40:15.593 回答
1

是的，这是可能的。不确定这个帖子是否仍然打开。但是您会想要执行 Excel Solver 加载项。发布所有数字，并在相邻单元格上加上 1。然后输入所需的输出编号..然后所有使用的数字将保持其相邻的“1”，而未使用的将变为“0”。然后做一个过滤公式，只列出旁边有“1”的那些。

于 2012-07-03T20:34:09.597 回答
1 
        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);
于 2011-08-02T15:46:36.183 回答