[fotelbujany]

#excel małe pytanko mam liczbę powiedzmy 20. Mam zbiór liczb które, tylko konkretne po zsumowaniu dadzą mi wynik czyli 20. Potrzebuje tych nieszczęsnych składników sumy dającej to 20. Da rady w Excel wyciągnąć te konkretne liczby jakąś formułą/formułami?

[5da4266d3de6dbaf425a2d4fc16225d0]

@fotelbujany: Obawiam sie ze problemem nie jest tu Excel tylko teoria złożoności obliczeniowej ( ͡° ͜ʖ ͡°) Problem który cię interesuje nazwywa się Subset Sum https://pl.wikipedia.org/wiki/Problem_sumy_podzbioru i jest NP-zupełny, czyli nie istnieje żadnen szybki (nie wykładniczy) algorytm, który ten problem rozwiązuje. Co więcej nawet udzielenie odpowiedzi czy w ogóle da się wybrać liczby które zsumują się do szukanej wartości (nawet bez wskazywania samych liczb) jest NP-zupełne.

[heniek_8]

@fotelbujany: możesz w vba napisać pętlę w pętli
Każdą z tych liczb mnożyć przez 0 lub 1 i sumować, jak wyjdzie 20 to gitara

For X1 = 0 to 1
For x2 = 0 to 1

Wynik = x1 * a + x2 * b
If wynik= 20 then print x1, x2

Next
Next

Czyli możesz dojść nawet do 2 do potęgi ile masz tych liczb, jeżeli jest ich dużo to

[fotelbujany]

@5da4266d3de6dbaf425a2d4fc16225d0: ech kurde ten zbiór liczb to jest max 20-50 liczb a sumę znam :( no nic jak pomysł kolegi @heniek_8 nie wypali to trudno trzeba będzie robić ręcznie w robocie.

[5da4266d3de6dbaf425a2d4fc16225d0]

@fotelbujany: Pomysł kolegi "wypali" tylko ze liczba podzbiorów wynosi 2^n czyli dla 50 liczb masz 2^50 możliwości do sprawdzenia a to ci się nie policzy. 2^20 zajmie kilka sekund, 2^30 kilka godzin. I bardzo chętnie zobaczę jak ty chcesz "ręcznie" zrobić coś takiego dla 50 liczb ( ͡° ͜ʖ ͡°)

[heniek_8]

@fotelbujany: ograniczaj ile się da liczbę tych składników
Np jak widzisz że któraś liczba jest większa od 20 to w ogóle nie rób dla niej pętli.
Każda dodatkowa liczba zwiększa czas wykonania dwukrotnie

[brak_nicku]

@fotelbujany: przy tak niewielkie liczbie składników solver powinien sobie dawać z tym radę bez problemów. Jak udostępnisz listę liczb (zbliżoną do rzeczywistych) i poszukiwaną sumę, to mogę prztetestować.

[fotelbujany]

@5da4266d3de6dbaf425a2d4fc16225d0: jasne rozumiem, spróbuję z tym pomysłem kolegi, zredukowanie tych liczb powiedzmy do tych 30 a nawet dużo mniej będzie w 90% przypadków możliwe, także nie jest to takie głupie, może się uda :)

[5da4266d3de6dbaf425a2d4fc16225d0]

przy tak niewielkie liczbie składników solver powinien sobie dawać z tym radę bez problemów

@brak_nicku: Pewny jesteś? 2^50 to nie jest niewielka liczba ( ͡° ͜ʖ ͡°) Polecam wykonać małe ćwiczenie i puścić sobie pętlę od 0 do 1073741824 (30 bitów) która będzie np. zwiększać licznik i zobaczyć ile coś takiego będzie się kręcić. Materiał poglądowy:

>> timeit.timeit(lambda: sum([1 for _ in range(2**20)]), number=1)

0.0583334993571043

>> timeit.timeit(lambda:

[cohontes]

@fotelbujany: solver

[brak_nicku]

@5da4266d3de6dbaf425a2d4fc16225d0: jestem prawie pewien, bo sporo tego typu rzeczy liczyłem. Problem będzie rozwiązywany metodą ewolucyjną, która:
a) nie gwarantuje, że rozwiązanie nawet jeśli istnieje zostanie znalezione
b) przy takiej liczbie zmiennych powinna się mimo a) bardzo dobrze sprawdzać

W międzyczasie przypomniało mi się, że istnieje algorytm (sam go nawet kiedyś miałem okazję wykorzystać), który działa w czasie O(N*X) i zawsze znajduje rozwiązanie, o ile istnieje. N to liczba elementów, X szukana

[5da4266d3de6dbaf425a2d4fc16225d0]

@brak_nicku: Wiadomo, zawsze można heurystycznie, tylko że wtedy może się nie znaleźć mimo że istnieje ;) Prawda że można to liczyć dynamicznie albo tak jak problem plecakowy, tylko że jeśli liczby nie są 0-10 tylko 32 albo 64 bitowe to robi niestety nic z tego nie będzie.

[brak_nicku]

@5da4266d3de6dbaf425a2d4fc16225d0: nudząc się sprawdziłem jak solver poradzi sobie z 50 losowymi liczbami z zakresu 1-200 i różnymi sumami - wynik zawsze był znajdowany w max 1-2 sekundy. Jest duża szansa, że znajdzie wynik optymalny lub bliski optymalnemu w czasie znacznie szybszym niż zrobi to człowiek. Deterministyczny algorytm, o którym wspomniałem da wynik 100% prawidłowy, ale przy wartościach sumy bliskich lub przekraczających 32-bit pewnie byłby nieefektywny, lub wymagał za dużo pamięci.

Jeśli