Algoritmo per trovare quali numeri da un elenco di dimensione n si sommano a un altro numero

Question

Ho un numero decimale (chiamiamolo obiettivo) e un array di altri numeri decimali (chiamiamo array elementi) e devo trovare tutte le combinazioni di numeri da elementi quale somma all'obiettivo.

Preferisco una soluzione in C# (.Net 2.0) ma possa vincere comunque il miglior algoritmo.

La firma del tuo metodo potrebbe essere simile a:

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

Answer 1

Risposte interessanti.Grazie per i suggerimenti su Wikipedia, sebbene interessanti, in realtà non risolvono il problema come affermato poiché stavo cercando corrispondenze esatte, più un problema di contabilità/bilanciamento dei libri che un tradizionale problema di imballaggio di contenitori/zaini.

Ho seguito con interesse lo sviluppo dello stack overflow e mi chiedevo quanto sarebbe stato utile.Questo problema si è presentato al lavoro e mi sono chiesto se l'overflow dello stack potesse fornire una risposta già pronta (o una risposta migliore) più velocemente di quanto avrei potuto scriverla io stesso.Grazie anche per i commenti che suggeriscono che questi compiti vengano contrassegnati come compiti a casa: immagino che sia ragionevolmente accurato alla luce di quanto sopra.

Per coloro che sono interessati, ecco la mia soluzione che utilizza la ricorsione (naturalmente). Ho anche cambiato idea sulla firma del metodo e ho scelto List> anziché decimal[][] come tipo restituito:

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

Se desideri che un'app testi il ​​funzionamento, prova questo codice dell'app 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();
    }
}

Spero che questo aiuti qualcun altro a ottenere la risposta più rapidamente (per i compiti o altro).

Saluti...

Answer 2

Il problema della somma dei sottoinsiemi e il problema dello zaino leggermente più generale vengono risolti con la programmazione dinamica:Non è richiesta l'enumerazione a forza bruta di tutte le combinazioni.Consulta Wikipedia o il tuo riferimento sugli algoritmi preferiti.

Sebbene i problemi siano NP-completi, sono molto "facili" NP-completi.La complessità algoritmica nel numero di elementi è bassa.

Answer 3

Penso che tu abbia un problema di imballaggio nel contenitore tra le tue mani (che è NP-difficile), quindi penso che l'unica soluzione sarà provare tutte le possibili combinazioni finché non ne troverai una che funzioni.

Modificare:Come sottolineato in un commento, non lo farai Sempre devo provare ogni combinazione per ogni insieme di numeri che incontri.Tuttavia, qualsiasi metodo che ti viene in mente ha serie di numeri dello scenario peggiore in cui tu Volere devo provare ogni combinazione - o almeno un sottoinsieme di combinazioni che cresce esponenzialmente con la dimensione dell'insieme.

Altrimenti non sarebbe NP-difficile.

Answer 4

Hai descritto a problema dello zaino, l'unica vera soluzione è la forza bruta.Esistono alcune soluzioni di approssimazione più veloci, ma potrebbero non soddisfare le tue esigenze.

Answer 5

Pur non risolvendo il problema della forza bruta (come altri hanno già menzionato), potresti prima ordinare i tuoi numeri e poi esaminare quelli possibili rimasti (poiché una volta superato il valore Somma, non puoi aggiungere alcun numero maggiore di Obiettivo - Somma).

Ciò cambierà il modo in cui implementi il ​​tuo algoritmo (per ordinare solo una volta e poi saltare gli elementi contrassegnati), ma in media migliorerebbe le prestazioni.

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