infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Simoiu Robert din Martie 20, 2010, 23:30:42

Titlul: Knapsack help
Scris de: Simoiu Robert din Martie 20, 2010, 23:30:42

Imi poate arata si mie de exemplu daca am N valori si vreau sa vad daca X se poate obtine adunand acele valori, cu algoritmul knapsack? Multumesc anticipat .

Titlul: Răspuns: Knapsack help
Scris de: George Popoiu din Martie 20, 2010, 23:47:06

Sunt 2 cazuri : cand poti aduna de mai multe ori aceeasi valoare si cand poti aduna fiecare valoare o singura data.

Care te intereseaza ?

Titlul: Răspuns: Knapsack help
Scris de: Simoiu Robert din Martie 20, 2010, 23:57:02

Aici e problema (http://infoarena.ro/problema/economie) .

Titlul: Răspuns: Knapsack help
Scris de: George Popoiu din Martie 21, 2010, 00:19:05

Citeste articolul cu solutii. O sa vezi ca nu e nevoie de Knapsack.

http://infoarena.ro/preoni-2008/runda-1/solutii#economie

Titlul: Răspuns: Knapsack help
Scris de: Simoiu Robert din Martie 21, 2010, 00:37:30

Am citit, dar nu stiu sigur, adica sa zicem pentru exemplul asta :

Cod:

Dau de 2, si ce fac, adica il bag intr-un vector si ce marchez ? Asta nu inteleg :-"

Titlul: Răspuns: Knapsack help
Scris de: Vlad Eugen Dornescu din Martie 27, 2010, 09:02:26

Din - vector in care tii 1, daca poti forma suma i si 0 daca n-o poti forma.

Cod:

Din[0] = 1 //e clar
for(i=1;i<=n;i++)
    if(Din[V[i]]==0) 
       {
            sol[++nrSol]=V[i]; //bagi in solutie daca nu se poate forma suma V[i]
            for(j=0;j<=V[n];j++) //cauti crescator sumele pe care le poti forma cu V[i] 
            //pentru ca poti folosi o moneda de mai multe ori
                    if(Din[j] && j+V[i]<=V[n]) //pana nu depasesti valoarea maxima a monedelor
                                 Din[j+V[i]]=1; //le marchezi 
       }