[javascript] znana suma, szukanie składników

[kurkusmaximus]

Mam "worek" z liczbami. Jak znaleźć składniki, które po dodaniu dadzą określoną sumę.
Np: w worku mam 100, 500, 400, 250, 700; użytkownik chce znaleźć składniki, które dadzą sumę 1000.

[Vax]

W ostateczności można brute force, jak masz w tablicy dane liczby, po kolei sprawdzasz, od a=1, do ilości liczb, czy dana liczba jest równa szukanej, potem szukasz, czy suma 2 jakichś da szukaną sumę, potem 3,4 aż do wielkości tablicy, oczywiście to jest najwolniejsza metoda

Pozdrawiam.

PS. Ten temat nadaje się do innego działu

[kurkusmaximus]

Dziękuję za przeniesienie do właściwego działu.

Czy istnieje jakiś wzór na szybkie znalezienie składników?

[argv]

Problem NP-Zupełny więc tak łatwo nie będzie.
Dynamik, w wersji 2d (można spokojnie zejść do 1d):

\(\displaystyle{ S}\) - nasz zbior liczb o mocy \(\displaystyle{ n}\).
\(\displaystyle{ B}\) - suma do uzyskania.

Robimy sobie tablice bool \(\displaystyle{ A[n+1][B+1] = \{false\}}\)
\(\displaystyle{ A[i,j]}\) = Czy istnieje podzbiór indeksow \(\displaystyle{ \{1..n\}}\) taki że \(\displaystyle{ \sum_{k \in S}^{} s_{k} = j}\)

Wzorek rekurencyjny:
\(\displaystyle{ A[i,j] = \begin{cases} true \Leftrightarrow A[i-1,j] \vee A[i-1,j-S] \\ false wpp \end{cases}}\)
+ startowo \(\displaystyle{ A[0,0] = true}\)

Odpowiedź to oczywiście \(\displaystyle{ A[n,B]}\). Odtworzenie sumy wygląda tak (praktycznie tak samo jak w problemie plecakowym bo są one w zasadzie prawie tym samym):

Kod: Zaznacz cały

   
        if(A[n][B] == false)
            printf("Brak rozwiazania
");
        else {    
            while(n > 0 && B > 0) {
                if(A[n][B] != A[n-1][B]) {
                    printf("%d ", S[n]);
                    sum -= S[n];
                }
                n--;
            }
            printf("
");
        }

Złożoność: \(\displaystyle{ O(nB)}\)