Algorytm znajdowania liczb z listy wielkości N sumy do innej liczby

Ciekawe odpowiedzi. Dziękuję za wskazówki do Wikipedii - choć interesujące - nie rozwiązują one problemu tak jak to powiedziałem, jak Szukałem dokładnych dopasowań - bardziej problemu księgowości / księgowości niż tradycyjnego problemu bin-packing / knapsack.

Śledziłem rozwój stack overflow z zainteresowaniem i zastanawiałem się, jak przydatny będzie. Ten problem pojawił się w pracy i zastanawiałem się, czy stack overflow może dostarczyć gotową odpowiedź (lub lepsza odpowiedź) szybciej niż sam mógłbym to napisać. Dzięki również za komentarze sugerujące to być tagged homework-myślę, że jest to dość dokładne w świetle powyższego.

Dla tych, którzy są zainteresowani, oto moje rozwiązanie, które wykorzystuje rekurencję (naturalnie) zmieniłem również zdanie o metodzie signature i poszedłem do List> zamiast dziesiętnego [] [] jako typ powrotu:

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

Jeśli chcesz, aby aplikacja przetestowała to działanie, wypróbuj ten kod aplikacji konsoli:

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

Mam nadzieję, że to pomaga komuś innemu szybciej uzyskać odpowiedź (czy to do pracy domowej, czy w inny sposób).