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.
[javascript] znana suma, szukanie składników
-
- Użytkownik
- Posty: 2
- Rejestracja: 20 wrz 2010, o 18:32
- Płeć: Mężczyzna
- Lokalizacja: polska
[javascript] znana suma, szukanie składników
Ostatnio zmieniony 20 wrz 2010, o 18:56 przez kurkusmaximus, łącznie zmieniany 2 razy.
- Vax
- Użytkownik
- Posty: 2913
- Rejestracja: 27 kwie 2010, o 22:07
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska / Warszawa
- Podziękował: 4 razy
- Pomógł: 612 razy
[javascript] znana suma, szukanie składników
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
Pozdrawiam.
PS. Ten temat nadaje się do innego działu
-
- Użytkownik
- Posty: 2
- Rejestracja: 20 wrz 2010, o 18:32
- Płeć: Mężczyzna
- Lokalizacja: polska
[javascript] znana suma, szukanie składników
Dziękuję za przeniesienie do właściwego działu.
Czy istnieje jakiś wzór na szybkie znalezienie składników?
Czy istnieje jakiś wzór na szybkie znalezienie składników?
- argv
- Użytkownik
- Posty: 569
- Rejestracja: 27 maja 2009, o 01:27
- Płeć: Mężczyzna
- Podziękował: 51 razy
- Pomógł: 66 razy
[javascript] znana suma, szukanie składników
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):
Złożoność: \(\displaystyle{ O(nB)}\)
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("
");
}