算法：如何找出在大小为n的列表中，哪些数字相加能得到另外一个指定的数字

Question

我有一个十进制数（我们称之为目标），以及由其他十进制数组成的数组（我们称之为元素），我需要找到所有加起来等于目标的元素的组合。

我偏好使用C# (.Net 2.0)的解决方案，但无论算法如何都可以。

您的方法签名可能如下所示：

public decimal[][] Solve(decimal goal, decimal[] elements)

- Sam Meldrum

Answer 1

有趣的答案。感谢您指出维基百科，虽然很有趣，但它们实际上并没有解决问题，因为我正在寻找精确匹配 - 这更像是一个会计/记账平衡问题，而不是传统的装箱/背包问题。

我一直关注着stackoverflow的发展，并想知道它会有多有用。这个问题在工作中出现了，我想知道stackoverflow能否提供一个现成的答案（或更好的答案），比我自己写得更快。感谢那些建议将此标记为作业的评论 - 鉴于以上情况，我想这是相当准确的。

对于那些感兴趣的人，这是我的解决方案，它使用递归（自然）我也改变了我的方法签名，选择了List>而不是decimal[][]作为返回类型：

public class Solver {

    private List<List<decimal>> mResults;

    public List<List<decimal>> Solve(decimal goal, decimal[] elements) {

        mResults = new List<List<decimal>>();
        RecursiveSolve(goal, 0.0m, 
            new List<decimal>(), new List<decimal>(elements), 0);
        return mResults; 
    }

    private void RecursiveSolve(decimal goal, decimal currentSum, 
        List<decimal> included, List<decimal> notIncluded, int startIndex) {

        for (int index = startIndex; index < notIncluded.Count; index++) {

            decimal nextValue = notIncluded[index];
            if (currentSum + nextValue == goal) {
                List<decimal> newResult = new List<decimal>(included);
                newResult.Add(nextValue);
                mResults.Add(newResult);
            }
            else if (currentSum + nextValue < goal) {
                List<decimal> nextIncluded = new List<decimal>(included);
                nextIncluded.Add(nextValue);
                List<decimal> nextNotIncluded = new List<decimal>(notIncluded);
                nextNotIncluded.Remove(nextValue);
                RecursiveSolve(goal, currentSum + nextValue,
                    nextIncluded, nextNotIncluded, startIndex++);
            }
        }
    }
}

如果您想测试此功能的应用程序，请尝试使用此控制台应用程序代码：

class Program {
    static void Main(string[] args) {

        string input;
        decimal goal;
        decimal element;

        do {
            Console.WriteLine("Please enter the goal:");
            input = Console.ReadLine();
        }
        while (!decimal.TryParse(input, out goal));

        Console.WriteLine("Please enter the elements (separated by spaces)");
        input = Console.ReadLine();
        string[] elementsText = input.Split(' ');
        List<decimal> elementsList = new List<decimal>();
        foreach (string elementText in elementsText) {
            if (decimal.TryParse(elementText, out element)) {
                elementsList.Add(element);
            }
        }

        Solver solver = new Solver();
        List<List<decimal>> results = solver.Solve(goal, elementsList.ToArray());
        foreach(List<decimal> result in results) {
            foreach (decimal value in result) {
                Console.Write("{0}\t", value);
            }
            Console.WriteLine();
        }


        Console.ReadLine();
    }
}

我希望这能帮助其他人更快地得到答案（无论是为了作业还是其他原因）。

祝好。

- Sam Meldrum

---

精确匹配是最接近的匹配。如果最接近的匹配不是精确匹配，则没有精确匹配。 - wnoise

感谢提供代码。我只需要一个解决方案，而不是所有可能性，所以我会尝试编辑代码... - Krip

好的，已编辑，使其在第一个解决方案处停止。如果需要的一些数字位于列表末尾，则性能会受到影响。 - Krip

谢谢您的回复，不好意思我有点递归无知，请问是否有一种方法可以在第一次匹配时就退出呢？或者如果只需要一个匹配，是否有更好的实现方式？ - PeterX

@SamMeldrum，您能否请看一下这个问题？https://dev59.com/YWoMtIcB2Jgan1znn9vq - Inside Man

Answer 2

我认为您手头有一个装箱问题（这是NP难问题），因此我认为唯一的解决方案就是尝试每种可能的组合，直到找到可行的方案。

编辑：正如评论中指出的那样，您不会总是需要尝试每个数字集合的每个组合。但是，无论您想出什么方法，都存在最坏情况下的数字集合，您将不得不尝试每种组合-或者至少是随着集合大小呈指数增长的子集组合。

否则，它就不会是NP难问题。

- Rob Dickerson

---

并不是每一个......一旦某个组合的总和超过了目标数字，您可以停止计算该分支并继续下一个。 - Haoest

Answer 3

子集和问题以及稍微更一般的背包问题，都可以用动态规划来解决：不需要枚举所有组合。请参考维基百科或您喜欢的算法参考资料。

尽管这些问题是NP完全问题，但它们是非常“容易”的NP完全问题。在元素数量方面的算法复杂度很低。

- Steve Jessop

Answer 4

您描述了背包问题，唯一的真正解决方案是暴力破解。有一些近似解决方案速度更快，但可能不适合您的需求。

- ARKBAN

Answer 5

虽然这并不能解决暴力破解的问题（正如其他人已经提到的），但你可以先将数字排序，然后再遍历剩下可能的数字（因为一旦你超过了Sum值，就无法添加任何大于Goal-Sum的数字）。

这将改变您实现算法的方式（为了仅排序一次，然后跳过标记的元素），但平均而言会提高性能。

- Adi

---

Adi，感谢你的建议。对于一般情况来说，这是一个很好的改进。但实际上，我的解决方案对于我遇到的问题更有效，只是我没有提供足够的信息让你知道。这些数字按日期顺序排列，并且更有可能按照这个顺序进行求和，因为日期对总数很重要。 - Sam Meldrum

Answer 6

public class Logic1 {
    static int val = 121;
    public static void main(String[] args)
    {
        f(new int[] {1,4,5,17,16,100,100}, 0, 0, "{");
    }

    static void f(int[] numbers, int index, int sum, String output)
    {
        System.out.println(output + " } = " + sum);
        //System.out.println("Index value1 is "+index);
        check (sum);
        if (index == numbers.length)
        {
            System.out.println(output + " } = " + sum);
            return;
        }

        // include numbers[index]
        f(numbers, index + 1, sum + numbers[index], output + " " + numbers[index]);
        check (sum);
        //System.out.println("Index value2 is "+index);
        // exclude numbers[index]
        f(numbers, index + 1, sum, output);
        check (sum);
    }

    static void check (int sum1)
    {
        if (sum1 == val)
            System.exit(0);
    }
}

- guest