Algorithme pour trouver les numéros à partir d'une liste de taille n somme vers un autre numéro

Des réponses intéressantes. Merci pour les liens vers wikipedia, s'ils sont intéressants: ils ne sont pas réellement résoudre le problème comme l'a déclaré que j'étais à la recherche de correspondances exactes - plus d'une comptabilité /livre blancing problème qu'une traditionnelle bin-packing /sac à dos de problème.

J'ai suivi le développement de débordement de pile avec intérêt et je me demandais s'il serait utile. Ce problème est venu au travail et je me demandais si un débordement de pile peut fournir un prêt à une réponse (ou une meilleure réponse) plus rapidement que je ne l'écrire moi-même. Merci aussi pour les commentaires suggérant cet être étiqueté devoirs, je pense que c'est assez exact, à la lumière de ce qui précède.

Pour ceux qui sont intéressés, voici ma solution qui utilise la récursivité (naturellement) j'ai aussi changé mon esprit à propos de la signature de la méthode, et est allé pour une Liste> plutôt que decimal[][] comme type de retour:

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

Si vous voulez une application pour tester cela fonctionne, essayez cette console le code de l'application:

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

J'espère que cela aide quelqu'un d'autre obtenir une réponse plus rapidement (que ce soit pour les devoirs ou autre).

Acclamations...

OriginalL'auteur Sam Meldrum

Je pense que vous avez une bin packing problème sur vos mains (ce qui est NP-dur), donc je pense que la seule solution va être d'essayer toutes les combinaisons possibles jusqu'à ce que vous trouver un qui fonctionne.

Edit: Comme l'a fait remarquer dans un commentaire, vous n'aurez pas toujours devez essayer chaque combinaison pour chaque série de chiffres que vous venez à travers. Cependant, n'importe quelle méthode que vous venez avec a scénario de la pire éventualité ensembles de nombres, où vous sera devez essayer chaque combinaison -- ou au moins un sous-ensemble de combinaisons qui croît de manière exponentielle avec la taille de l'ensemble.

Sinon, il ne serait pas un problème NP-difficile.

OriginalL'auteur Rob Dickerson

Alors que pas de résoudre le problème de la force brutale (comme déjà mentionné) vous pouvez trier vos numéros d'abord, puis allez sur la liste de gauche (car une fois que vous avez passé la Somme de la valeur, vous ne pouvez pas ajouter n'importe quel nombre plus grand que le But de la Somme).

Cela va changer la façon dont vous mettez en œuvre votre algorithme (dans l'ordre de tri seule fois, puis passez les éléments marqués), mais dans la moyenne, une amélioration des performances.

OriginalL'auteur Adi