Come trovare quali numeri in un set si sommano a un altro numero dato?

Question

Ecco un problema che sembra stia funzionando con un sistema di contabilità.

Ho una serie di transazioni, ma la loro somma non è uguale all'importo che il dipartimento contabilità dovrebbe ritenere opportuno. Non mettono in discussione la matematica, ma solo le transazioni incluse: p

Esiste un algoritmo che mi aiuterebbe a determinare quali transazioni nel set non dovrebbero essere incluse affinché la somma corrisponda a un determinato importo.

Given Set:  
2  
4  
5  
7

Given Sum Amount:
13

Result Set:
2
4
7

Modifica Ci sono meno di 100 transazioni nel set. Qualcuno ha un esempio C # in quanto non ce n'è uno sul Risolvere il NP-complete problema nella domanda XKCD ?

Amico, avrei dovuto ottenere una laurea in CS.

Answer 1

Questo è il problema Sum del sottoinsieme , che è NP-Complete . Ma ciò non significa che non esiste un algoritmo per trovare una somma di sottoinsieme.

Answer 2

Questo è il Problema dello zaino ed è NP-Complete. Non lo risolverai facilmente esattamente con qualsiasi cosa tranne che per piccoli set di input. Per qualsiasi set di problemi di dimensioni decenti, è uno di quei problemi della vita dell'universo da risolvere.

Detto questo, ci sono risolutori di zaini con algoritmo genetico là fuori.

Answer 3

Come hanno detto i membri precedenti, questo è il problema Somma sottoinsieme (o problema con lo zaino). Tuttavia, dire che non può essere fatto in modo efficiente non è molto preciso. Si può fare, semplicemente no in tempo polinomiale. La soluzione è in realtà abbastanza semplice usando la programmazione dinamica e ricorsione (e in tempo pseudo-polinomiale).

Dati interi [a_1, ..., a_n] e un numero T,

Definisce l'array S [i, k] per indicare se c'è un sottoinsieme di elementi tra a_1, ... a_i che si sommano a k. (Questa è una matrice binaria).

Possiamo quindi definire una relazione ricorsiva come segue:

S [i, k] = S [i-1, k] o S [i-1, k-a_j]

In parole, questo significa che usiamo l'elemento a_i o no. La risposta si troverà in S [n, T].

Qual è il carico di lavoro per costruire la matrice S? Bene, S ha n * T elementi. Per calcolare ogni elemento, dobbiamo fare O (1) lavoro. Quindi la corsa completa il tempo è O (n * T).

Ora a questo punto, sembra che io abbia provato P = NP, come questo sembra essere un algoritmo temporale polinomiale. Tuttavia, ricorda che misuriamo la dimensione dell'input in binario, quindi T = 2 ^ p per alcuni p.

Non credo che qualcuno direbbe la soluzione sopra, quando implementato correttamente è irragionevole. In effetti, per molti dimensioni ragionevoli del problema, funzionerà egregiamente.

Inoltre, ci sono alcune euristiche per risolvere questo problema, ma lo sono non un esperto in quella zona.

Answer 4

Questa è una versione di il problema dello zaino . È NP completo, quindi non otterrai una buona risposta generale. Quanto sono grandi le tue serie di transazioni? È 5 come hai mostrato o è più simile a 500?

Answer 5

OK. Molte persone hanno dato il nome al problema e menzionato quanto NP sia difficile. E in generale, sono corretti. Tuttavia, hai un caso molto specifico che devi risolvere. La prima domanda da porsi è se ritieni che le tue 100 transazioni siano vicine a quelle giuste. Hai un totale ("il tuo" totale). Hanno un totale. ("reale" totale). Alcune delle tue transazioni sono quindi fasulle. Se sospetti che ci siano solo alcune transazioni fasulle, allora non è così male. Ad esempio, consideriamo il caso in cui esiste una sola transazione fasulla. In tal caso, dovremmo solo controllare 100 numeri diversi. Se ci sono 2 trans falsi, allora stai esaminando 100 * 99 assegni e le cose diventeranno pazze con 4 trans falsi, con quasi 100.000.000 di passaggi. anche se tutto ciò che stai facendo è aggiungere alcuni int non è troppo terribile.

Un'altra possibile scorciatoia è esaminare la natura dei tuoi dati (per inciso, è possibile pubblicare i 100 "numeri" e la somma prevista?). Quanto è la tua somma rispetto alla somma reale? Ci sono valori così grandi che eliminarli renderebbe la tua somma improvvisamente inferiore alla somma reale? Se è così, sai che quei valori non possono essere falsi. Ad esempio, nel tuo esempio, 7 è assolutamente necessario.

Answer 6

        bool bBreak = false;
        int iEnd = 13;
        ArrayList ar1 = new ArrayList();
        ar1.Add(2);
        ar1.Add(4);
        ar1.Add(5);
        ar1.Add(7);

        String s1 = " ";
        foreach (int i in ar1)
        {
            if (i == iEnd)
            {
                s1 = "Result = " + i;
                bBreak = true;
            }
            if (bBreak) break;
            ArrayList ar2 = new ArrayList();
            ar2.AddRange(ar1);
            ar2.Remove(i);
            foreach (int j in ar2)
            {
                if ((i + j) == iEnd)
                {
                    s1 = "Results = " + i + ", " + j;
                    bBreak = true;
                }

                if (bBreak) break;
                ArrayList ar3 = new ArrayList();
                ar3.AddRange(ar2);
                ar3.Remove(j);
                foreach (int k in ar3)
                {
                    if (bBreak) break;
                    if ((i + j + k) == iEnd)
                    {
                        s1 = "Results = " + i + ", " + j + ", " + k;
                        bBreak = true;
                    }
                }
            }
        }
        Console.WriteLine(s1);

Answer 7

Sì, questo è possibile. Non sono sicuro che questo post sia ancora aperto. Ma vorresti fare il componente aggiuntivo Risolutore Excel. Pubblica tutti i numeri, con 1s nella cella adiacente. Quindi inserisci il numero di output desiderato ... quindi tutti i numeri utilizzati, manterranno i loro "1" adiacenti, mentre quelli inutilizzati si trasformeranno in "0". Quindi esegui una formula di filtro che elenca solo quelli che hanno un " 1 " accanto ad esso.