Algorithme pour trouver quels nombres d'une liste de taille n somme à un autre nombre

Question

J'ai un nombre décimal (appelons-le objectif ) et un tableau d'autres nombres décimaux (appelons le tableau éléments ) et il me faut trouver toutes les combinaisons. des nombres de éléments qui totalisent l'objectif.

J'ai une préférence pour une solution en C # (.Net 2.0), mais le meilleur algorithme peut-il l'emporter malgré tout.

La signature de votre méthode peut ressembler à quelque chose comme:

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

Answer 1

Réponses intéressantes. Merci pour les liens vers Wikipedia - bien qu’intéressants - ils ne résolvent pas le problème comme indiqué car je cherchais des correspondances exactes - il s’agit davantage d’un problème de comptabilité / d’équilibrage de livres que d’un problème traditionnel d’emballage de sacs / sac à dos.

J'ai suivi avec intérêt le développement du débordement de pile et je me suis demandé à quel point il serait utile. Ce problème est apparu au travail et je me suis demandé si le dépassement de capacité de pile pouvait fournir une réponse toute faite (ou une meilleure réponse) plus rapidement que je ne pourrais l'écrire moi-même. Merci également pour les commentaires suggérant que cela soit étiqueté comme un devoir - je suppose que cela est raisonnablement précis à 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 également changé d'avis à propos de la signature de la méthode et j'ai opté pour List > plutôt que décimal [] [] 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 souhaitez qu'une application teste cela fonctionne, essayez ce code d'application de la console:

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 aidera quelqu'un d'autre à obtenir sa réponse plus rapidement (que ce soit pour faire ses devoirs ou autrement).

A bientôt ...

Answer 2

Le problème de la sous-somme et le problème un peu plus général du sac à dos sont résolus par la programmation dynamique: l'énumération en force brute de toutes les combinaisons n'est pas requise. Consultez Wikipedia ou la référence de votre algorithme préféré.

Bien que les problèmes soient NP-complets, ils sont très "faciles". NP-complet. La complexité algorithmique du nombre d’éléments est faible.

Answer 3

Je pense que vous avez un problème d'emballage de bac sur votre main (qui est NP -hard), donc je pense que la seule solution sera d'essayer toutes les combinaisons possibles jusqu'à ce que vous en trouviez une qui fonctionne.

Modifier: comme indiqué dans un commentaire, toujours ne devez pas essayer toutes les combinaisons pour tous les ensembles de nombres que vous venez à travers. Cependant, chaque méthode que vous proposez comporte des ensembles de nombres dans le pire des scénarios, dans lesquels vous devrez essayer toutes les combinaisons - ou au moins un sous-ensemble de combinaisons qui s'agrandit. de manière exponentielle avec la taille de l'ensemble.

Sinon, ce ne serait pas difficile.

Answer 4

Vous venez de décrire un problème de sac à dos , la seule véritable solution est la force brutale. Certaines solutions d'approximation sont plus rapides, mais peuvent ne pas répondre à vos besoins.

Answer 5

Tout en ne résolvant pas le problème de la force brute (comme d’autres l'ont déjà mentionné), vous voudrez peut-être d'abord trier vos nombres, puis passer en revue les nombres possibles restants (une fois que vous avez passé la valeur de Sum, vous ne pouvez pas ajouter de nombre plus grand que l'objectif - somme).

Cela modifiera la façon dont vous implémenterez votre algorithme (afin de trier une seule fois puis d'ignorer les éléments marqués), mais améliorera en moyenne les performances.

Answer 6

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