13

我有一个十进制数（我们称之为目标）和一个其他十进制数的数组（我们称之为数组元素），我需要从总和为目标的元素中找到所有数字组合。

我偏爱 C# (.Net 2.0) 中的解决方案，但无论如何最好的算法都可能获胜。

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

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

6 回答 6

13

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

我一直在关注堆栈溢出的发展，并想知道它会有多大用处。这个问题出现在工作中，我想知道堆栈溢出是否可以比我自己编写更快地提供现成的答案（或更好的答案）。还要感谢建议将其标记为作业的评论-鉴于上述情况，我想这是相当准确的。

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

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

干杯...

于 2008-09-17T15:00:49.207 回答
3

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

编辑：正如评论中指出的那样，您不必总是为遇到的每组数字尝试每种组合。但是，您提出的任何方法都有最坏情况下的数字集，您必须尝试每种组合 - 或者至少是随着集合大小呈指数增长的组合子集。

否则，它不会是 NP 难的。

于 2008-09-17T14:05:03.053 回答
3

子集和问题以及稍微更一般的背包问题通过动态规划来解决：不需要对所有组合进行暴力枚举。请查阅 Wikipedia 或您最喜欢的算法参考。

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

于 2008-09-17T14:22:21.423 回答
2

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

于 2008-09-17T14:05:21.820 回答
2

虽然没有解决蛮力问题（正如其他人已经提到的那样），但您可能希望先对数字进行排序，然后检查剩下的可能数字（因为一旦通过 Sum 值，您就不能添加任何大于 Goal 的数字 -和）。

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

于 2008-09-17T16:44:13.250 回答
-1 
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);
    }
}
于 2010-04-13T11:34:58.143 回答