Algorytm, który sprawdza wszystkie możliwości dodawania

Question

Zadanie: Mamy liczby załóżmy póki  A,B,C,D,E(wektorowo) Liczba =[x][y]

A = [3][7]

B = [4][6]

C = [6][9]

D = [1][0]

E = [2][2]

Pytanie: Czy jest jakiś sposób ,aby zapisać w pamięci podręcznej wszystkie możliwe kombinacje dodawania każdego x i każdego y? Ale nie tylko dla 5 liczb ale i dla np. 1000. Czyli:

x=  3 + 4 + 6 + 1 + 2 =16    ALE I TEŻ MIESZANIE     x= 3+6+2=11

x=3+4+6+1=14                                                            x=3+4+1=8

x=3+4+6=13                                                               itd...

x=3+4=7

x=3

 

*To samo w przypadku y

 

Nie wiem czy dobrze przekazałem o co mi chodzi, w każdym razie będę wdzięczny za wszelką pomoc.

Answer 1

Wygląda to na proste wyznaczenie wszystkich kombinacji bez powtórzeń i zsumowanie elementów każdej kombinacji z osobna.

Osobiście wpadłem na pomysł z maską liczb wchodzących do sumowania w postaci liczby dwójkowej z ilością cyfr taką jak ilość x lub y.

Przykład

Dla x:
Maska: 00001 Suma: 3
Maska: 00010 Suma: 4
Maska: 00011 Suma: 3 + 4 = 7
Maska: 00100 Suma: 6
itd...

To samo dla y.

Comments

Obliczyłeś te wszystkie sumy dla miliona x i y? A jak wyglądał czas wykonywania programu oraz jego zużycie pamięci?

---

no właśnie tu jest problem, póki co mam rozwiązanie z maską i nie wiem czy wrzucać do sprawdzarki, pogadam z profesorem w poniedziałek i zadecyduje, póki co daje naj :) dzięki bardzo

---

swoją drogą jestem ciekaw jak to sprawdzarka ogarnie :)

---

Wydaję mi się, że dla takiej ilości kombinacji nie wystarczy ci ani miejsca w RAM-ie, ani na dysku twardym, ani czasu na oczekiwanie na wynik, ale mogę się mylić. Czekam na rezultaty 

---

w takim razie w poniedziałek o 22 dam znać :) Ja tych zadań nie układałem , więc mam związane ręce :) Pewnie jest inny sposób na zrobienie tego, jak cie to interesuje to wpisz w googla "olimpiada informatyczna" i zadanie Pionek :) Pozdrawiam i jeszcze raz dziękuje :)