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

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

方法签名可能类似于：

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

解决方案

回答

我认为手上有一个垃圾箱包装问题(这是NP难题)，所以我认为唯一的解决方案是尝试所有可能的组合，直到找到可行的组合。

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

否则，这将不是NP难题。

回答

我们已经描述了背包问题，唯一真正的解决办法是蛮力。有些近似解决方案速度更快，但可能无法满足需求。

回答

通过动态编程可以解决子集和问题以及更为普遍的背包问题：不需要对所有组合进行强力枚举。请查阅Wikipedia或者我们最喜欢的算法参考。

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

回答

有趣的答案。谢谢我们提供指向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();
    }
}

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

干杯...

回答

在不解决暴力破解问题(如其他人已经提到的问题)的同时，我们可能希望先对数字进行排序，然后再对剩余的数字进行排序(因为一旦传递了总和值，就不能添加比目标总和大的数字)。

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

回答

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