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

Tak, to jest dobry pomysł w takim układzie można obliczyć, że liczebność zbioru będzie sięgać 31 (bo nie liczę sumy 0 elementów). I już widać, że zrobienie czegoś takiego dla 1000 liczb byłoby zbyt czasochłonne i pamięciożerne.

---

Wg mnie jest to jedno z wydajniejszych rozwiązań. Dla 1000 elementów wystarczy posiadać maskę 1000-elementową, w skrócie 1000 bitów / 8 = 125 bajtów. Nie są to zawrotne wielkości, i tak zapewne do takich liczb nigdy jego program nie dojdzie.

Do opisu swojego algorytmu dodam, że sumę elementów można liczyć z poniższej pętli

#include <cstdlib>

// ...

int index_tab = 0;
while (maska != 0)
{
	if (maska % 2)
	{
		// Dodanie danego elementu do sumy itp.
	}
	maska = div(maska, 2).quot;
	index_tab++;
}

Kod działa na zasadzie wyznaczania kolejnych cyfr maski (od jedności), jeśli dana cyfra jest jedynką, to dodajemy dany element do sumy, jeśli nie, to ten element omijamy. Później obcinamy wyznaczoną cyfrę, inkrementujemy indeks tablicy i algorytm idzie dalej.

Na zewnątrz tej pętli inkrementujemy oryginał maski (ta powyżej była jedynie roboczą kopią) i również powtarzamy kod od nowa, aż maska nie będzie miała wartości

2 ^ ilość_cyfr

---

Tak, ale jeżeli chcesz obliczyć i przechowywać obliczenia wszystkich takich sum dla 1000 liczb to już sam wiesz jak dużo pamięci byś zużył (2 ^ 1000 sum musiałbyś zrobić). Sama maska jest ok i to świetny pomysł ale liczba możliwych do utworzenia sum staje się przytłaczająca.

---

Nic na to nie poradzę. Matematyka rządzi się swoimi prawami i rzeczywiście liczba sum przy 1000 elementach jest przytłaczająca, no ale nie dotyczy to mojej odpowiedzi, a jedynie problematyki pytania samej w sobie.

---

Jego pytanie brzmi " Czy jest jakiś sposób ,aby zapisać w pamięci podręcznej wszystkie możliwe kombinacje dodawania każdego x i każdego y? " dlatego o tym piszę. Przy małych liczbach da się, ale przy dużych już nie ma tak łatwo.

Z drugiej strony ciekawe do czego to jest potrzebne.

---

rzeczywiście wypróbowałem sposób i jest klarowny jednak ja potrzebuje przedział do miliona, potrzebne mi to jest do zadania, które już obmyślałem teoretycznie.

---

rano zobaczę jeszcze jak to wychodzi w sprawdzarce i dam naj. dziękuje bardzo

---

Milion x i y? I chcesz wyznaczyć sumy dla wszystkich kombinacji? Wydaję mi się, że jest to czasowo i pamięciowo niemożliwe dla zwykłego komputera, ale możesz próbować.

---

Tak naprawdę postawienie pytania w inny sposób, pozwala zaproponować mniej zachłanne na zasoby algorytmy. Np.

1. Czy daną wartość sumy można "zbudować" poprzez kombinację bez powtórzeń z liczb?

2. Ile razy wartość występuje pośród sum możliwych do zbudowania z podanych liczb?

3. Jak szybko wyznaczyć podaną sumę spośród liczb?

Nie znam(y) problemu więc jeśli chcesz generować wszystkie sumy, wynikowy kontener może być duży. Zdefiniuj co chcesz zrobić. Być może będzie efektywniejszy i mniej łapczywy na pamięć algorytm :-)

---

Znaczy w punktacji mam w kryteriach punktowania  do miliona, dlatego taki nacisk na to kładę, a sumy mi są potrzebne, żeby wybrać potem z wyniku dodawania x^2+y^2 największy wynik, to jest tegoroczne zadanie z olimpiady, z którym właśnie sobie poradziłem :)

---

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 :)