从大小为 n 的列表中找出哪些数字和另一个数字相加的算法 [英] Algorithm to find which numbers from a list of size n sum to another number

问题描述

我有一个十进制数(我们称之为目标)和一个其他十进制数的数组(我们称之为数组元素)，我需要找到所有的组合来自元素的总和为目标的数字.

I have a decimal number (let's call it goal) and an array of other decimal numbers (let's call the array elements) and I need to find all the combinations of numbers from elements which sum to goal.

我更喜欢 C# (.Net 2.0) 中的解决方案，但无论如何最好的算法可能会获胜.

I have a preference for a solution in C# (.Net 2.0) but may the best algorithm win irrespective.

您的方法签名可能类似于:

Your method signature might look something like:

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

推荐答案

有趣的答案.感谢您对维基百科的指点——虽然很有趣——他们实际上并没有像我在寻找精确匹配那样解决问题——更多的是会计/账簿平衡问题，而不是传统的装箱/背包问题.

Interesting answers. Thank you for the pointers to Wikipedia - whilst interesting - they don't actually solve the problem as stated as I was looking for exact matches - more of an accounting/book balancing problem than a traditional bin-packing / knapsack problem.

我一直很感兴趣地关注堆栈溢出的发展，并想知道它会有多大用处.这个问题在工作中出现，我想知道堆栈溢出是否可以比我自己编写的更快地提供现成的答案(或更好的答案).也感谢建议将此标记为家庭作业的评论 - 根据上述情况，我想这是相当准确的.

I have been following the development of stack overflow with interest and wondered how useful it would be. This problem came up at work and I wondered whether stack overflow could provide a ready-made answer (or a better answer) quicker than I could write it myself. Thanks also for the comments suggesting this be tagged homework - I guess that is reasonably accurate in light of the above.

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

For those who are interested, here is my solution which uses recursion (naturally) I also changed my mind about the method signature and went for List> rather than decimal[][] as the return type:

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

如果你想要一个应用来测试它是否有效，试试这个控制台应用代码:

If you want an app to test this works, try this console app code:

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}	", value);
            }
            Console.WriteLine();
        }


        Console.ReadLine();
    }
}

我希望这能帮助其他人更快地得到答案(无论是家庭作业还是其他).

I hope this helps someone else get their answer more quickly (whether for homework or otherwise).

干杯...

这篇关于从大小为 n 的列表中找出哪些数字和另一个数字相加的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！