从大小为n的列表中找出哪些数字求和的算法

  • Z时代
  • 2024-01-10
  • 分类：问答

我有一个十进制数字（我们称其为 ）和一个其他十进制数字的数组（我们称为数组 ），并且我需要找到从总和到目标的

所有数字的组合。

我偏爱使用C＃（.Net 2.0）解决方案，但最好的算法可能会赢得胜利。

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

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

回答：

有趣的答案。感谢您提供的指向Wikipedia的指针-尽管很有趣-但实际上并没有解决我在寻找精确匹配时所指出的问题-

与传统的装箱/背包问题相比，更多的是会计/账簿平衡问题。

我一直关注着堆栈溢出的发展，想知道它的用处。这个问题在工作中出现，我想知道堆栈溢出是否可以比我自己编写更快地提供现成的答案（或更佳的答案）。也感谢您提出的建议将此作业标记为作业的评论-

鉴于上述情况，我认为这是相当准确的。

对于那些有兴趣的人，这是我的使用递归的解决方案（自然地），我也改变了对方法签名的看法，并选择了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();
    }
}

我希望这可以帮助其他人更快地得到答案（无论是用于家庭作业还是其他）。

干杯…

以上是 从大小为n的列表中找出哪些数字求和的算法 的全部内容， 来源链接： utcz.com/qa/403848.html

回到顶部