Zebughil .. nice one

[•flo_demon]

Nu stiu daca sunt reguli impotriva topicurilor de genu asta:P da se pare ca mai sunt.
Prob o fo faina   ..si din cate am observat si comuna la grupele X, XI-XII
Am ramas dezamagit ca nu mi-o iesit  si surprins de ce nu...
Multzi au patzit asa...

Daca atzi facuto cum atzi facuto? si de ce nu e bine asa: (prea mult pana se posteaza articol)

de ex. eu am considerat asa: a = nr minim de camioane spre a transporta greutatea i. (obtinuta din insumarea greutatii pietrelor selectate)

cu o dinamica de genu:

Cod:

  for (int i = 1; i <= n; ++i)
    {
        for (int j = G*n - z[i]; j; --j)
        {
            if (a[j])
            {
                if (z[i] + j <= a[j]*G)
                    k = 0;
                else k = 1;
                if (a[j+z[i]] > a[j] + k || a[j+z[i]] == 0)
                    a[j+z[i]] = a[j] + k;
            }       
        }    
        if (!a[z[i]]) a[z[i]] = 1;
    }

si rasounsul era in a unjde s suma greutatii pietrelor... si G cat poate duce un camion

hmm.. de ce nu e bine...? daca puteti da ceva idei despre cum se rezolva sau  de ce nu e bine asa i would aprieciate it  

si un test consnsistent daca se poate..pls....macar primul...sau oricare...mor daca nu aflu cum se rezolva...    

[andreit1]

Dinamica se foloseste doar dupa ce ai demonstrat( sau e evident) ca este si buna. Ceea ce faci tu acolo mi se pare ceva cam greedy mai degraba... Problema se putea rezolva de max chiar si cu backtracking, in locul unei dinamici nesigure...
Un test( oarecare) care poate te va convinge ca nu e bun programu tau:
17 100
12 16 14 18 17 19 10 18 16 14 9 6 3 4 2 10 1
17 9
8 9 9 9 5 9 9 9 1 3 3 3 4 9 8 9 1
17 10
10 8 5 4 4 3 8 5 7 2 5 4 2 7 4 3 2
Mie imi da 2,12,9.

[•Marius]

Algoritmul meu suna cam asa:  am obtinut Greedy + cautare binara (sirul este sortat descrescator) un numar de submultimi, apoi am incercat cu un BKT sa imbunatatesc! 8 teste au mers, inclusiv cel al lui andreit1. De ce nu am luat si primele doua teste nu stiu...  

[andreit1]

Solutia greedy nu iti da intotdeauna solutia optima. Si inca o chestia... un back bine facut iti da intotdeauna rezultatul bun( daca il lasi sa mearga pana la capat). Uite-te si peste solutiile oficiale daca vrei niste solutii mai destepte.

[•flo_demon]

Da tot 2, 12 9 imi da si mie...
am cerut un test din cele oficiale daca se poate...
si am ramas surprins ca ai spus ca e greedy  :lol:  

wow... no offence...da e dinamica 100%  :lol:  :lol:  :lol:  :lol:  
deci am putea primi un test?

[andreit1]

E regula de nu stiu cand... NU SE DAU TESTELE OFICIALE!
Cand despre dinamica ta... Ce dinamica e aia cand nu obtii rezultatul bun intotdeauna? Programarea dinamica presupune si corectitudine... Altfel parerea mea e ca tot greedy e.

[•flo_demon]

o well daca nu se dau teste ... sorry...topic closed din partea mea

[cristi8]

tot vorbiti de back, ca se lua maxim cu back.. cum faceati back-ul, ca eu cand m-am gandit nu mi-a venit nici o idee.

[u-92]

un back de 90 de puncte e asta:
caut binar nr. minim de camioane, pt un astfel de numar am sum = suma
greutatilor din camionul i.
Pe rand, incerc sa plasez pietrele in camioanele in care pot, adik z[k] + sum <= G (k e indicele pietrei curente). Cand am ajuns la pozitia N si am reusit sa o plasez si pe asta e clar ca am obtinut solutie. Daca nu obtin solutie, caut un numar mai mare de camioane.

[cristi8]

aaaa, back() d-ala ca-n manualul de clasa 10a..

..era mai misto cu permutari cum e prezentat in articol

[andreit1]

Doar ca algoritmul cu permutari este O(N!) pur... Ca sa nu mai cauti binar puteai sa faci asa... Considerai la inceput un singur camion, in care puneai greutatea 1.  Si dupa ai la fiecare pas( pentru fiecare greutate) incercai sa il pui in unul din camionele anterioare sau singur intr-un camion noi. Cam asta e algoritmul... cu cateva chestii in plus scadea foarte mult sunt N!.

[•LucAnd]

Am facut si eu problema cu programare dimamica si pe moment solutia mi s-a parut buna dar cred ca am uitat ceva si am luat numa 10 p am sa ma mai uit peste problema si am sa vad daca pot sa o fac sa mearga
practic ce faceam :
luam vectorul cu greutait si incercam sa aflu pe rand la ficare bucata cu care din cele precedente dadea o suma cat mai mare fara sa treaca peste limita maxima si blocu primea valoarea sumei , si retineam intr-un vector predecesorul lui
pe urma din vectoru blocurilor cautam cea mai buna solutie si ii marcam elementele ca vizitate , faceam asta pana erau transportate toate blocurile
solutia are dificultate n*n dar la unele teste imi iese cu un tir in plus (la majoritatea nu da din trei unu nu merge) cre ca am uitat eu o posibilitate , voi credeti ca am vreo sansa sa o fac 100%??

[ditzone]

Nu ai sanse sa obtii punctaj maxim cu o astfel de solutie "greedy"
Ia de exemplu testul

Cod:

6 100
33 33 33 60 60 60

tu vei obtine raspunsul 4 deoarece initial vei baga 33 33 33 intrun camion si vei mai folosi inca 3 pentru a transporta si pietrele de 60. Raspunsul optim este 3 deoarece se transporta cate un 33 cu un 60. (daca am inteles eu bine ce faceai....)

[VladS]

Problema e NP-completa asa ca nu exista algoritmi polinomiali. Deci dinamicile alea care de fapt sunt greedy  nu sunt corecte.

[•cri-kee]

Eu zic asa.
1. sortam vectorul descrescator
2. pornim de la 1 pana la n si incercam sa "cumplam" elementul i cu multimea cu suma maxima (ne uitam la tot ce se afla inaintea lui i) de pana acum.
That's it!

Pentru ca nu am fost tocmai explicita.. ar veni ceva de genul:

Cod:

{initializari etc etc}
for i:=1 to n do
 multime[i]:=i;


for i:=1 to n do
begin
  max:=0;
  pozmax:=0;
  for j:=1 to i-1 do
    if (max<suma[j]) and (suma[j]+v[i]<=volCamion) then
       begin
          max:=suma[j];
          pozmax:=j;
       end;
end;
  
{si-acuma, daca e cazul, facem uniunea de multimi. scuzati-ma dar am cam multa treaba in seara asta si recunosc, mi-e si cam lene sa scriu}

   
[/code]

[cristi8]

tu n-auzi ca nu se poate face corect polinomial ?? ce nu intelegi ?!

[•azotlichid]

ati putea incerca sa va uitati pe solutia oficiala  
http://info.devnet.ro/articole.php?page=art&art=74&artpage=5

[•FreeYourMind]

Pai, la zebughil mergea intr-adevar un fel de back... cu adancimea maxima n.
De fapt e generare de permutari, numai ca are mult mai putin de n!
Adica punem primul element in multimea 1, al doilea in 1 si 2, al treilea in 1,2,3 s.a.m.d.   Dar ca sa nu ne ajungem la n! adica sa facem verificarilela dupa ce am grupat toate n blocuri in camioane, vedem la momentul dat daca putem adauga sau nu. Asta reduce simtitor timpul.
Adica pastram intr-o matrice greutatea curenta a unui camion. La inserarea unui bloc vedem, daca acesta poate fi inserat sau nu in camionul i.
am facut asa si am luat 100.
Si ca sa mearga si mai repede: Avem asa, daca numarul de camioane curente e mai mare decat best (nr cel mai mic de camioane care a fost determinat pana acum ca solutie, nu neaparat cea mai buna), atunci exit;
initinial best este egal cu n.

[•cristy]

mai fratilor...voi ziceti ca nu se poate cu greedy...da eu am incercat totusi...sunt greu de cap...am incercat asa...sortez greutatile descrescator...pun primu bloc in primu camion...si apoi...verific fiecare greutate daca nu poate fi pusa in vreunul din camioanele dinainte, in caz afirmativ, pun blocul in primul camion in care incape..si daca nu incape in nici unul...o pun in alt camion...asta ar fi rezolvarea...de ce nu e buna?...pls...dati si mie un exemplu...ca tot nu ma prind...iau numa 40 de pct...restu...WA...si imi intra in 0.02 secunde...cel mai mult...mie mi se pare buna rezolvarea...

[•greco]

Daca vi s-a spus un lucru, de ce insistati la infinit ? Problema asta e NP-completa, si NU se poate rezolva cu greedy. E clar lucrul asta.

Nu te astepta sa-ti dam contraexemple la solutiile tale, pentru ca cu exemplele poti realiza un singur lucru: sa spui ca o solutie e proasta daca nu le trece. NU si invers. Ok ?

[•FreeYourMind]

cristy si greco:
eu am facut problema ca si cristi, plus cu conditia sa verificam sa nu folosim mai mult de best camioane. unde best reprezinta numarul cel mai bun de camioane gasit. Un bloc nou incercam sa il punem in fiecare din camioanele dinainte, sau intr-unul nou. Se cerceteaza toate cazurile deci nu ma prind de ce e asta greedy. Si inca o observatie (i might be wrong, ). Se poate de sortat initial in ordine crescatoare!
Dupa parerea mea... daca sortezi crescator, camioanele se umplu mai greu deci primul best are sanse mari sa fie destul de mic, si mai apoi nu va mai trebui sa exploram prea in adancime!  Am luat maximul asa, de ce ziceti ca nu merge?
p.s. initial best este n, logic.

[•greco]

Daca ai luat maxim nu inseamna ca ai rezolvat-o. Inseamna ca ai facut o rezolvare pe care au mers testele.

[ditzone]

Freeyourmind... ceea ce ai facut tu incearca toate posibilitatile... este backtracking.. Ceea ce a facut cristy este greedy pentru ca el cand plaseaza o piatra intr-un camion nu mai incearca si in altul.. si nu va obtine mereu solutia optima..
Incercati sa vedeti si solutiile de la:  http://info.devnet.ro/articole.php?page=art&art=74&artpage=5

[•FreeYourMind]

ok, thx de observatii. eu intr-adevar credeam ca cristi incearca in toate camioanele anterioare.  
si observatia lui greco e binevenita.  

[•Zeus]

Pai asta denota teste proaste spre f. proaste, daca se poate lua maxim cu rezolvari din astea dubioase. Erau 3 subteste pe test, era destul de usor sa pici rezolvari din astea. Macar pe un test, sa stie lumea ca solutia lor nu e corecta  :lol:

Incep sa inteleg propunerea ginfo ca sa existe teste submitate de concurenti ...