Kako iz niza izdvojiti clanove koji zadovoljavaju odredjeni uslov?

[maddog]

Mozda se iz naslova moze zakljuciti da je ovo jednostavan problem,
ali mislim da resenje nije toliko jednostavno, barem ne meni.

PROBLEM:
Imamo niz elemenata u kome se neki elementi mogu ponavljati npr. {6,3,3,2,2}.
Iz ovog niza treba izdvojiti one clanove koji zajedno daju zbir sto blizi nekoj konstanti, npr. 10,
i formirati novi niz. To raditi sve dok iz pocetnog niza ne nestane elemenata.

Glavni problem kod ovoga je da ukoliko zbir izdvojenih elementi iz niza nemoze biti jednak konstanti,
treba to uraditi tako da ostane sto manje do dopune konstante. Znaci treba sto idealnije rasporediti
elemente iz pocetnog niza u nove nizove, pri cemu novonastali nizovi ne moraju imati isti broj elemenata.

Konkretno kod datog primera, ocigledno je, NIZ1{6,2,2} NIZ2{3,3}

Nemam konkretu ideju za resenje ovog problema, razmisljao sam u ovom pravcu:

vezem se za prvi element, a onda prodjem kroz niz i dodajem elemente dok ne dostignem zadatu konstantu,
ali to onda nije idealna kombinacija...

Ima li neko ideju za resenje ovog problema??? Nije obavezno koristiti nizove, poenta je da gomilu
elemenata rasporedim u grupe tako da njihov zbir bude sto idealniji nekoj konstanti.

[Zepi]

Imamo niz elemenata u kome se neki elementi mogu ponavljati npr. {6,3,3,2,2}.
Iz ovog niza treba izdvojiti one clanove koji zajedno daju zbir sto blizi nekoj konstanti, npr. 10,
i formirati novi niz. To raditi sve dok iz pocetnog niza ne nestane elemenata.

Konkretno potrebno je još podataka da bi moglo da se nađe najefikasnije rešenje.

Glavno pitanje da li se odvajaju samo grupe istih elemenata ili mogu biti i različiti ali da im je suma što bliže konstanti.

Konkretno kod datog primera, ocigledno je, NIZ1{6,2,2} NIZ2{3,3}

Vidim da si izdvojio niz2{3,3} pa pretpostavljam da izdvajaš grupe istih elemenata. Zanima me zbog čega ako ti je konstanta 10, nisi izdvojio i 6 jel je isto blizu kao i 3+3. Mislim nisam shvatio još najbolje zadatak. Pojasni ga na još nekom primeru.

Uglavnom radi se dinamičkim nizovima tj. dimenzija im se konstantno menja. Već je bilo napomene da za ovakve probleme je definitivno najbolje koristiti LISTE i metode ugrađene u njih. Pogledaj malo šta se sve može uraditi sa listama na sledećem linku pa vidi da li bi ti nešto ovako odgovaralo.

http://www.cppreference.com/wiki/stl/list/start

Znaci treba sto idealnije rasporediti
elemente iz pocetnog niza u nove nizove, pri cemu novonastali nizovi ne moraju imati isti broj elemenata.

Konkretno šta ovo znači tj. da ne moraju da imaju isti broj elemenata. Pojasni malo.

[Marko Аcović]

Napisi neki primer ulaznog niza (sa vecim brojem elemenata) kao i krajnji niz koji treba da se dobije pa da vidimo. Btw, imas li tacnu postavku zadatka?

[maddog]

Glavno pitanje da li se odvajaju samo grupe istih elemenata ili mogu biti i različiti ali da im je suma što bliže konstanti.

Nebitno je da li su elementi isti, poenta je samo da budu ubaceni u grupu tako da njihov zbir bude sto blizi konstanti

Vidim da si izdvojio niz2{3,3} pa pretpostavljam da izdvajaš grupe istih elemenata. Zanima me zbog čega ako ti je konstanta 10, nisi izdvojio i 6 jel je isto blizu kao i 3+3. Mislim nisam shvatio još najbolje zadatak. Pojasni ga na još nekom primeru.

NIZ1{6,2,2} - izdvojio sam prvo niz u kome je zbir elemenata jednak konstanti, a NIZ2{3,3} je samo ono sto je ostalo od pocetnog niza

Napisi neki primer ulaznog niza (sa vecim brojem elemenata) kao i krajnji niz koji treba da se dobije pa da vidimo. Btw, imas li tacnu postavku zadatka?

Konkretno, postavka problema je sledeca:

- Imamo jednu duz, tacnije imamo gomilu duzi iste velicine, ali predpostavimo da je to jedna, zbog lakseg razumevanja problema

- Treba da je izdelimo na nove duzi, tako da sto manje materijala otpadne.

Jos konkretnije, rec je o PVC i ALU profilima koje majstor treba da isece na komade, ali tako da mu sto manje materijala otpadne, i da ne mora ceo dan da sedi sa papirom i olovkom, i racuna kojim redom da sece komade...

Nadam se da je postavka sada malo razumljivija 

Uglavnom radi se dinamičkim nizovima tj. dimenzija im se konstantno menja. Već je bilo napomene da za ovakve probleme je definitivno najbolje koristiti LISTE i metode ugrađene u njih. Pogledaj malo šta se sve može uraditi sa listama na sledećem linku pa vidi da li bi ti nešto ovako odgovaralo.

Samo da ja vidim kako da grupisem elemente, a realizaciju cu lako  , posto ovo ne bi trebalo da bude neki bogzna kakav projekat, mislo sam da ga odradim kao MFC Dialog, i u njemu cu preko List kontrole dodavati i izbacivati elemente. Btw, hvala za link.

[Zepi]

Znači primena programskih jezika u praksi, to je i poenta.

E ako je tako evo jedna ideja na brzinu, ipak je vikend pa se valja malo i odmarati za dolazeću radnu nedelju 

Prvo sortiraj niz u ne rastućem redosledu tj. od najvećeg ka najmanjem. Moraćeš u svakom trenutku da znaš vrednost najmanjeg i najvećeg elementa niza a to ti je najkaše ako ga sortiraš.

Kreni od početka niza i prebacuj elemente u novi niz ili listu ako im je suma jednaka konstanti ili <= od ( konstante - minimalni element ).

Ovaj drugi uslov ti je da ako naiđeš na problem {6.3.2.2} znači ne smeš da dodaš 6+3 jer sa 6+2+2=10 dobijaš rešenje.

Postavićeš i jednu logičku promenljivu na false i proveravati je za slučaj da ne nađeš idealnu kombinaciju i ponoviš logiku sa doavanjem elemenata dok im je suma < 10. Pošto je niz sortiran prvi element koji se doda a da je suma manja od konstante bi trebalo da bude idealno rešenje tj, da ima najmanje otpadaka.

Ovo je na brzinu smišljeno ali bi trebalo da pokrije veliki deo ovog problema. Istestiraj u praksi pa javi 

Pozdrav

[holodoc]

Istestiraj u praksi pa javi

Sun-ova Java ili neka druga?

[maddog]

Odok da cukam...

[maddog]

Hmm... Nisam bash uspeo da se snadjem sa ovim listama...

Zasto nemoze sledeci kod da radi kako treba?

Kod Izaberi Expand


list<int> lista;
list<int> lista_new;

list<int>::iterator temp=lista.begin();
list<int>::iterator prvi=lista_new.begin();

while(temp != lista.end())
{

lista_new.insert(prvi,*lista.begin());
lista.pop_front();

temp++;
}


Ne prijavljuje kompajler greshke, ali kad se pokrene program, ide cuveno "Don`t send".

Hteo sam da prodjem kroz pocetnu listu, i dodam prvi element u novu listu, a zatim da izbacim prvi clan pocetne liste.

Ovde ima josh nekih uslova iz Zepi-evog predloga, ali moram priznati da nisam najbolje razumeo kako ce mi to obezbediti idealnu kombinaciju.

Elem, da je prvo vidim sta je sa ovim parcetom koda, a posle cu se vec nekako snaci...

[Zepi]

Meni nema Dont send ali kod koji si okačio neće nista da radi. Ne znam šta imaš van ovog koda tj. kad popunjavas elemente liste što je veom avažno zbog kreiranja iteratora.

Ono što je veoma važno kada se radi sa listama je da kada kreiraš iterator moraš da vodiš računa da ga kreiraš kada u listi ima barem neki element. Ako prvo kreiraš iterator pa tek onda popunjavaš listu, nikada nećeš ući u onu while petlju. Barem su takva moja iskustva sa listama u c++ jeziku.

Takođe nakon svake promene liste vrati iterator na list.begin() da bi ga dalje koristio.

[maddog]

Kada sam konacno uspeo da nadjem vremena za ovaj zadatak, naisao sam na problem

Da li je ovo

Kod Izaberi Expand


CString t;
CString strItem.Empty();

//lista je vec uneta

lista.sort();
lista.reverse();

list<int> lista_new;
list<int>::iterator newIterator;

list<int>::iterator poslednji;
list<int>::iterator temp=lista.begin();
list<int>::iterator pom;

bool check=false;

while(temp != lista.end())
{

poslednji=lista.end(); --poslednji;

if(GetSuma(lista_new)+*temp==10 || GetSuma(lista_new)+*temp<=10-*poslednji)
{
newIterator = lista_new.begin();
lista_new.insert(newIterator,*temp);
newIterator = lista_new.begin();
lista.erase(temp);
temp=lista.begin();
if(GetSuma(lista_new)>=10-*poslednji && GetSuma(lista_new)<=10) check=true;
}

else
{
++temp;
}

if(check==true)
{

for( pom = lista_new.begin(); pom != lista_new.end();pom++)
{
lvi.mask = LVIF_TEXT;
t.Format("%d mm, ",*pom);
strItem.Insert(strItem.GetLength(),t);
lvi.iItem = m_cInputData.GetItemCount();
lvi.iSubItem = 0;
lvi.pszText = (LPTSTR)(LPCTSTR)(strItem);
}

m_cOutputData.InsertItem(&lvi);

strItem.Empty();
t.Empty();
lista_new.clear();
check=false;
}
}

/*
LVITEM lvi;
CListCtrl m_cOutputData;
*/


slicno ovome???

Prvo sortiraj niz u ne rastućem redosledu tj. od najvećeg ka najmanjem. Moraćeš u svakom trenutku da znaš vrednost najmanjeg i najvećeg elementa niza a to ti je najkaše ako ga sortiraš.

Kreni od početka niza i prebacuj elemente u novi niz ili listu ako im je suma jednaka konstanti ili <= od ( konstante - minimalni element ).

Ovaj drugi uslov ti je da ako naiđeš na problem {6.3.2.2} znači ne smeš da dodaš 6+3 jer sa 6+2+2=10 dobijaš rešenje.

Postavićeš i jednu logičku promenljivu na false i proveravati je za slučaj da ne nađeš idealnu kombinaciju i ponoviš logiku sa doavanjem elemenata dok im je suma < 10. Pošto je niz sortiran prvi element koji se doda a da je suma manja od konstante bi trebalo da bude idealno rešenje tj, da ima najmanje otpadaka.

Mora da ima neka ocigledna greska, koju ja nevidim 
Za primer {6,3,3,2,2} mi daje resenje, {6,2}

[Zepi]

Ovako pogledano na brzinu izgleda ok.

Ako možeš okači ceo kod pa da ga propustim kroz kompajler korak po korak i istestiram. Možda je greška negde van ovog okačenog koda.

Pogledaću sutra detaljnije.

[maddog]

Evo koda...

Ne znam da li treba da kazem da je jos u razvoju...