infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: ditzone din Noiembrie 19, 2005, 16:06:50

Titlul: 133 Zebughil
Scris de: ditzone din Noiembrie 19, 2005, 16:06:50

Aici puteÅ£i discuta despre problema Zebughil (http://infoarena.ro/problema/zebughil).

Titlul: 133 Zebughil
Scris de: Marius Stroe din Noiembrie 19, 2005, 17:03:58

Problema este NP ? Eu am sortat pietrele lui Zebughil descrescator si am creat Greedy un numar de submultimi. Pentru a fi sigur am verificat cu BKT , dar am obtinut 80 p, raspuns incorect la primele doua teste...
Pentru toate testele pe care le-am dat BKT a gasit cu o submultime mai putin.

Titlul: 133 Zebughil
Scris de: VladS din Noiembrie 19, 2005, 17:08:09

E cumva Multiple Knapsack Problem ?

Titlul: 133 Zebughil
Scris de: Cosmin Negruseri din Noiembrie 19, 2005, 17:20:35

Da, e. :)

Titlul: 133 Zebughil
Scris de: Ciocas Radu din Februarie 15, 2006, 23:36:50

?! generarea de permutari ? pai pt. n=17 sunt f multe permutari, poate ma ajuta cineva cu o sugestie caci eu nu vad cum pot fi generate atat de multe permutari cu backtracking. (in stiva se incarca camioane incarcate sau blocuri?)

Titlul: 133 Zebughil
Scris de: u-92 din Februarie 15, 2006, 23:53:01

exista solutia oficiala
http://info.devnet.ro/articole.php?page=art&art=74&artpage=5

Titlul: 133 Zebughil
Scris de: Ciocas Radu din Februarie 15, 2006, 23:57:09

normal ca aia am citit-o prima oara, nu am inteles mare lucru de aia am postat, in fine mersi oricum

Titlul: 133 Zebughil
Scris de: Marius Stroe din Februarie 16, 2006, 00:02:20

Daca rezolvi problema asa nu obtii punctaj maxim, deoarece sunt foarte multe permutari - cum ai zis si tu - iar complexitate mai mica de O(N!) nu poti sa obtii! :P Permutarile blocurilor lui Zebughil le poti genera cu metoda backtracking intr-un singur vector de lungime N... Pentru fiecare permutare poti sa testezi Greedy de cate camioane ai nevoie printr-o parcugere (astfel ajungi la O(N! * N)): daca in camion are loc si blocul curent atunci il pui, altfel mai numeri un camion si pui blocul curent in el; apoi treci evident la urmatorul bloc. :thumbup:

Titlul: 133 Zebughil
Scris de: u-92 din Februarie 16, 2006, 00:02:27

daca faci un bkt nu generezi chiar toate permutarile, mai bagi niste optimizari. si asa scade foarte mult complexitatea de la n!

Titlul: 133 Zebughil
Scris de: Cosmin Negruseri din Februarie 16, 2006, 09:16:43

Ce nu e clar la solutia oficiala?

Titlul: 133 Zebughil
Scris de: Ciocas Radu din Februarie 16, 2006, 22:57:17

Citat din mesajul lui: Cosmin

Ce nu e clar la solutia oficiala?

Nu mi-e clar cum sa generez cu back permutarile(sa intre cat de cat in timp), eu am generat permutarile folosind un vector in care retin daca e prezent deja un element din multime in permutare sau nu +testare greedy la fiecare, nu inteleg cum ar putea intra in timp cu permutari...(sorry daca postez aiurea dar nu am unde cere ajutor :P )

Titlul: 133 Zebughil
Scris de: VladS din Februarie 17, 2006, 00:59:05

N-ai cum sa iei punctaj mare cu O( n * n ! ). Trebuie sa faci O( 2 ^ n * n )
Daca vrei totusi sa exersezi o implementare la generare permutari uite un pseudocod destul de eficient:

Cod:

se afiseaza permutarea identica p[i]=i;
i=n-1
repeta
   daca (p[i]<p[i+1]) atunci
      1 determina j(pornind de la n,j--) astfel incat p[j]>p[i];
      2 schimba p[i] cu p[j]
      3 inverseaza elem subvectorului p[i+1], p[i+2]...p[n]
      4 afiseaza vectorul p
      5 i=n-1
   altfel i=i-1
cattimp(i>0)

Sau mai simplu, poti sa faci cu next_permutation din STL. ex (http://www.sgi.com/tech/stl/next_permutation.html)

Titlul: 133 Zebughil
Scris de: Bogdan-Cristian Tataroiu din Februarie 17, 2006, 12:40:21

Se poate lua punctaj maxim cu O(N! * N) cu un back la care trebuie un optimizezi ceva mic :P.... Si nu merge sa faci aceeasi smecherie pentru codul acela care determina permutarile postat mai sus...

Solutia oficiala este O(2 ^ N * N ^ 2) sau O(2 ^ N * N) si te sfatuiesc sa citesti articolul cu solutii si sa vezi cum se face... Iti va fi mult mai util daca faci aceasta solutie decat un back :)

Titlul: RÄƒspuns: 133 Zebughil
Scris de: Gabriel Bitis din Martie 29, 2007, 19:33:36

imi puteti da niste teste.. sa ma verific... eu zic ca am facut un algoritm destul de bun incat sa gaseasca raspunsurile, chiar daca nu ar intra in timp.. totusi.. vreau sa compar niste raspunsuri

Titlul: RÄƒspuns: 133 Zebughil
Scris de: Paul-Dan Baltescu din Martie 29, 2007, 21:18:32

Test:

Cod:

6 20
1 1 1 1 1 1
8 20
4 6 12 5 9 11 11 3
10 30
13 21 9 2 3 2 1 7 10 9

Raspuns:

Cod:

1
4
3

Titlul: RÄƒspuns: 133 Zebughil
Scris de: Gabriel Bitis din Martie 30, 2007, 11:02:32

multumesc pentru teste.. acum iau 20 ](*,) .. adica ultimele 2 teste..la restul imi da raspuns gresit... nu stiu c am gresit.. poate daca imi dati niste teste putin mai complicate : :'(

Titlul: RÄƒspuns: 133 Zebughil
Scris de: Paul-Dan Baltescu din Martie 30, 2007, 13:05:32

Cod:

17 92
81 28 38 10 14 2 30 30 90 91 29 39 13 1 2 3 77 
16 27
8 8 8 3 2 1 9 10 12 10 20 21 23 14 14 13
15 10
1 2 2 2 8 8 3 9 4 10 1 5 5 6 4

Cod:

7
7
7

Nu e foarte greu sa faci un generator si un brute la problema asta. Ai putea incerca sa ti-o testezi singur.

Titlul: Răspuns: 133 Zebughil
Scris de: Florian Marcu din Martie 05, 2009, 14:25:27

Ar putea cineva binevoitor sa dezvolte putin paragraful asta din articolul cu solutii ?

Citat

Deoarece fie folosim maxim n camioane fie nu avem solutie putem incerca construirea unei matrici best(i,j) cu semnificatia cat mai este liber in ultimul camion ca sa avem transportati bitii de 1 din i si sa folosim maxim j camioane. Completarea acestei matrici se face in O((2^n)*(n^2)), aducand 100 de puncte.

Nu inteleg prea bine la ce ma ajuta sa stiu "cat mai este liber in ultimul camion ca sa avem transportati bitii de 1 din i si sa folosim maxim j camioane", pt a afla solutia problemei. De asemenea, nu vad nici cum as putea obtine aceastra matrice. Multumesc anticipat!

Titlul: RÄƒspuns: 133 Zebughil
Scris de: Gabriel Bitis din Martie 05, 2009, 17:56:43

La ce te ajuta chestia aia : sa zicem ca ai best[i ][j] = X -> inseamna ca pana acum ai incarcat blocurile corespunzatori bitilor de 1 din i, si ai folosit j camioane, iar in ultimul camion mai poti baga greutatea X.
Din starea asta iei fiecare bloc k (1 <= k <= N) care nu a fost incarcat ((1<<k) & i == 0) si il incarci. Daca intra in camionul j, atunci ajungi in starea best[i + (1<<k)][j], altfel mai folosesti un camion si ajungi in best[i + (1<<k)][j + 1].