如何找到一组中的数字加到另一个给定的数字？

Question

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

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

是否有一种算法可以帮助我确定不应该包含集合中的哪些事务，以使总和与给定数量相匹配。

Given Set:  
2  
4  
5  
7

Given Sum Amount:
13

Result Set:
2
4
7

修改 集合中的交易少于100个。有没有人有一个C＃示例，因为解决NP-complete问题没有XKCD中的问题问题？

男，我应该获得CS学位。

Answer 1

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

Answer 2

这是背包问题，它是NP-Complete。除了小输入集之外，你不会轻易地解决它。对于任何体面大小的问题集，它都是宇宙生命解决问题中的一个。

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

Answer 3

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

给定整数[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，就像这样 似乎是一个多项式时间算法。但是，请记住 我们用二进制测量输入大小，所以T = 2 ^ p 第

我认为没有人会说上述解决方案的时候 正确实施是不合理的。事实上，对很多人而言 合理的问题规模，它将表现令人钦佩。

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

Answer 4

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

Answer 5

行。很多人都给出了问题的名称，并提到了NP难的问题。一般来说，他们是正确的。但是，您需要解决一个非常具体的案例。要问的第一个问题是，您认为您的100笔交易是否接近正确的交易。你有一些总数（“你的”总数）。他们总共有一些。 （“真实的”总数）。因此，您的一些交易是虚假的。如果您怀疑那里只有少数虚假交易，那么这并不是那么糟糕。例如，让我们考虑只有一个虚假交易的情况。在这种情况下，我们只需要检查100个不同的数字。如果有2个伪造的转换，那么你正在看100 * 99的检查，并且在4个虚假的反式中，事情会变得疯狂，几乎有100,000,000步。虽然如果你所做的只是添加一些并不太可怕的int。

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

Answer 6

        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);

Answer 7

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