Mam ciagzbior elementow A_1, A_2, A_3,...,A_n i liczbe X. Jak odnaleŹć w ciaguzbiorze A jak najmniejsza liczbe elementow ktorych suma da mi X. Zwracam sie o pomoc lub jakas podpowiedz bo ja juz nie mysle ostatnio... Jesli problem jest banalny/opisany w masie literatury/do znalezienie w google/whatever to z gory przepraszam...
0
1
Jeśli dobrze rozumiem to co napisałeś to nazywa się to Problem sumy podzbioru i jest NP-zupełne (właściwie problem który opisałeś jest utrudnieniem tego problemu, bo chcesz mieć najmniejszą liczbę elementów)
http://pl.wikipedia.org/wiki/Problem_sumy_podzbioru
http://en.wikipedia.org/wiki/Subset_sum_problem
0
Idealnie zrozumiales :) Przynajmniej jest punkt zaczepienia... Uprosci cos jesli moje X = sum(A) % B ? (gdzie sum(A) to suma wszystkich elementow tego zbioru)
0
Jeżeli liczby A_1, A_2, A_3,...,A_n są naturalne to da się to zrobić szybko.
0
Z ciekawości zapytam, temat związany z zadaniem ze SPOJa? :P
0
- Tak, sa naturalne, rozwin temat jesli mozesz...
- Tak troche, nie do konca spoj ale blisko, ale nie jest to problem sam w sobie.
1
http://pl.wikipedia.org/wiki/Problem_wydawania_reszty
Mam nadzieję, że pomogłem :)
0
Bardzo pomogles, wiedzialem ze problem jest banalny... Program juz prawie ukonczony :)