[Arhitekta]

Arhitekta:
Prvo sortiras blokove na sledeci nacin. Dva bloka sortiras tako da ti 'gore' bude onaj da bude vec nosivost. Ako imas blok a i b, onda gledas gde je veca nosivost, kad je a na b ili b na a. Tako sortiras i onda radis DP (znam da ovo ne pomaze bas puno samo DP i ne napisati kako), ali pokusaj pa ako ne uspes objasnicu kako se radi :)

Shta je DP? Samo shta je ta skratjenica, ne pada mi na pamet shta bi to moglo biti. Demokratska Partija. Ili Dikstri nije, dinamichko mozhda.

DP <=> dinamicko programiranje...
Kad sortiras na onaj nacin, onda si siguran da redosled u optimalnom slaganju je isti kao i reodlsed u sortiranom nizu (naravno ne moraju ici blokovi jedan za drugim u sortiranom nizu, ali kad se izbace oni koje nisi koristio bas tako ih dobijas)...

Okej, razumem da se svaka dva bloka, ako mogu da ikako stanu jedan na drugi, to rade na jedan, najbolji nachin. Razmislitju malo o tome josh..

Probao sam sa DPom ranije, ovom logikom: Ako predpostavimo da vetj imam k blokova goji grade tu najvetju kulu, k+1vi blok tje biti onaj kome je nosivost najblizha broju (nosivost kule - tezhina tog bloka). Tako se najmanje gubi na nosivosti kule, i samom tim kula ostaje sa najboljnom nosivoshtju. Medjutim, ovo bi bilo reshenje kada bi imao beskonachno mnogo svakog od blokova.

E sad, kod knapsack-a postoje varijante sa po jednim i beskonachno svakog predmeta. Od ove varijante sa beskonachno mnogo svakog predmeta se lako dolazi do ove druge, tako shto uvedem josh neku "dinamichku" dimenziju: koristim sve predmete sa indeksima (1..j) gde j raste do ukupnog broja predmeta. Ali ne chini mi se da bi ista dogradnja radila na mom reshenju, iako su knapsack i ovaj sa ciglama jako slichni problemi.

Pa ja bas ne bih to svrstao u knapsack, ako bih bas morao onda bih pre rekao da lici na najduzi rastuci/opadajuci podniz (izmenjen naravno), ali mozda je ne rezonujem dobro...

Da ne kucam kod, da li je ovo reshenje:
Postavim sve cigle u usmereni graf, tako da su 1 i b u vezi ako se a mozhe staviti na b, i ukoliko b mozhe na a onda je to nepovoljnije reshenje
Zatim topoloshki sortiram u neki niz tako da je niz[1] cigle koja se ne mozhe staviti ni na jednu drugu (valjda postoji takva)
onda uradim prolaz korz taj niz i brzo dodjem do reshenja DPom..

?

Ne znam kako ces doci do resenja cak i ako postoji takva cigla (koja ne mora obavezno da postoji) i kako ces pamtiti da li na nekoj k-oj cigli nisi presao granicu nosivosti za recimo 1 ciglu... Ja i dalje ostajem pri DP. Nisam siguran da ovako moze da se uradi :)

Istina.

Muka mi je svega, reci mi. Porazhen sam :)

Ides redom kroz sortiran niz i ovo sto pisem dole gledas za svaki ciglu.
Recimo da imas naslagano optimalno do visine k.
Prvo probas da pokusas da napravis visinu k + 1 od i-te cigle, bez obzira da li mozes ili ne pokusavas i za visinu k i k - 1 ... 1 i vidis da li ti je bolje da stavis i-tu na vrh, umesto te koja stoji (gledas kakva bi nosivost bila da stavis tu umesto te sto stoji, ako bi bila veca, onda mu pricinis jedan update :) )
Nadam se da je sad jasno. Probaj na papir da ispises ovo sto sam ti objasnio. Ostala je jos samo implementacija, ideju sam celu izlozio :p

Jel imash MSN Messenger? Ili neshto slichno, poshto imam dosta pitanja a ovo je stvarno spora i ogranichena komunikacija.. Ili ako imash neshto slichno.. mail naprimer

e-mail? Ja to ne koristim, sta ce mi to ;)
Salim se naravno... boba5555@gmail.com. Ako si na gmail-u mozemo chatovati pa ce ti biti lakse.
Pa sad bi trebalo da ti bude mnogo lakse, jedino kod da ti posaljem :)

Nemam gmail account, a tamo kazhe da ga mogu dobiti ako me neko pozove. Moj mail je boca@yubc.net, pa me pozovi.

Reshio sam prokleti zadatak. Nisam razumeo onaj sort, i to mi je bio problem; mislio sam da ne postoji red u kome se cigle mogu sortirati tako da a lezhi na b ukoliko je a > b. Inache, taj sort jeste topoloshki sort na neki nachin. Definicija top sorta je jednaka ovom rasporedu cigala: ako a ide posle b, onda je a > b.

Enivej, velika hvala!

[q]Dva bloka sortiras tako da ti 'gore' bude onaj da bude vec nosivost. Ako imas blok a i b, onda gledas gde je veca nosivost, kad je a na b ili b na a[/q]

Ne kuzim ovo, jel pri sortiranju 2 bloka gledas samo koji ima vecu nosivost (i ignoriras tezine), ili gledas dal je bolje nosivost(a) - tezina(b) ili (nosivost(b) - tezina(a). Jel ti veca nosivost u skupu od k blokova znaci nosivost od k-tog bloka ili od prvog - suma tezina[drugog..k-tog]. I sta ako se a ne moze stavit na b zbog tezine. Pojasni malo plz...

modovi, jel moze jedan split ove dve teme na delioce i arhitektu? :)

imas recimo blokove a i b..
U slucaju da ti se oba nadju u optimalnom resenju, sta je bolje ? Da a bude iznad b, ili obrnuto ?
ono sto znas je da ce zbir njihovih tezina biti isti...
Ali, gledas da ih postavis tako da je ispod.nosivost - iznad.tezina > iznad.nosivost - ispod.tezina...
Pa, kada tako sortiras, onda mozes da radis dinamicko..

[quote author=Sanja Popovic link=topic=10269.msg11829#msg11829 date=1176501084]
modovi, jel moze jedan split ove dve teme na delioce i arhitektu? :)
[/q]
moze ;)

Meni pada na 4. i 9. test primeru.
Evo dio koda:

  sort(b.begin(), b.end(), mojsort);  //sortiranje na vec spomenut nacin
  memset(dp, -1, sizeof(dp)); //na pocetku su sve nosivosti -1 tj. ne postoji kula visine > 0
  for(int i = 0; i < n; ++i) {
    for(int j = i; j >= 0; --j) {
      if(!j) dp[1] >?= b[i].n;  //ako stavis na prazno onda bolje uzet blok najvece nosivosti
      else dp[j+1] >?= dp[j] - b[i].t;  //inace stavi taj blok ako bi time povecao nosivost kule od j+1 blokova
    } 
  }
  int sol = 0;
  for(int i = 1; i <= n &amp;&amp; dp[i] >= 0; ++i) sol = i; //nadji najvisu kulu koja ima nosivost >= 0
  printf("%d", sol); 

greska je ovde :

else dp[j+1] >?= dp[j] - b[i].t;  //inace stavi taj blok ako bi time povecao nosivost kule od j+1 blokova

treba biti

else dp[j+1] >?= (dp[j] - b[i].t) <? b[i].n;  //inace stavi taj blok ako bi time povecao nosivost kule od j+1 blokova

Fala Relja care.

uh, nekako sam shvatio kako se radi dinamicki , ali mi puca za test primer 8, jel bi mogao neko da mi ga posalje ?

Sort(n);
int nosivosti[5001];
memset(nosivosti,-1,5002);
for(int i = 1; i <= n; i++)
{
for(int j = i+1; j >= 1; j--)
{        
if(j==1) { if(cigle[i].n>=nosivosti[j]) nosivosti[j] = cigle[i].n;}
else if(nosivosti[j]<min(nosivosti[j-1]-cigle[i].t,cigle[i].n))
nosivosti[j] = min(nosivosti[j-1]-cigle[i].t,cigle[i].n);
}        
}
for(br = 1; br <= n;br++)
if(nosivosti[br]<0) break;

Jel mogu da dobijem najmanji od primera 4,5,6,8,9. Na vremenu prolazi ali ne i tacan rez. Stvarno nemam ideju zasto. Jel moze neko da pogleda da li mi je dobro sortiranje(ono pod repeat-om) jer mi ovo posle valja 99%. moj mail je nemanja.90@nadlanu.com

meni rade samo 1,2, 10, zastoooooo?