如何找出一组中的哪些数字与另一个给定的数字相加？

Question

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

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

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

Given Set:  
2  
4  
5  
7

Given Sum Amount:
13

Result Set:
2
4
7

编辑： 该集中的交易数量少于 100 笔。 有没有人有一个 C# 示例，因为 解决 NP 完全问题上没有一个示例XKCD问题问题？

老兄，我应该获得计算机科学学位。

Answer 1

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

Answer 2

这就是背包问题，它是NP完全问题。 除了小输入集之外，您无法轻松地用任何东西精确地解决它。 对于任何规模相当大的问题集来说，它都是一生中需要解决的问题之一。

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

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，要么不使用元素 a_i 。
答案位于 S[n,T]。

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

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

我认为没有人会说上述解决方案，当
执行不当是不合理的。 事实上，对于很多人来说
合理的问题规模，它将表现出色。

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

Answer 4

这是背包问题的一个版本。 它是 NP 完全的，所以你不会得到一个好的通用答案。 您的交易集有多大？ 是像你展示的那样 5 还是更像 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”的公式。