ditzone
Vizitator
|
|
« : Noiembrie 19, 2005, 16:06:50 » |
|
Aici puteţi discuta despre problema Zebughil.
|
|
|
Memorat
|
|
|
|
•Marius
|
|
« Răspunde #1 : 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.
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
VladS
Vizitator
|
|
« Răspunde #2 : Noiembrie 19, 2005, 17:08:09 » |
|
E cumva Multiple Knapsack Problem ?
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #3 : Noiembrie 19, 2005, 17:20:35 » |
|
Da, e.
|
|
|
Memorat
|
|
|
|
•hitmann
Strain
Karma: 2
Deconectat
Mesaje: 14
|
|
« Răspunde #4 : 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?)
|
|
|
Memorat
|
|
|
|
u-92
Vizitator
|
|
« Răspunde #5 : Februarie 15, 2006, 23:53:01 » |
|
|
|
|
Memorat
|
|
|
|
•hitmann
Strain
Karma: 2
Deconectat
Mesaje: 14
|
|
« Răspunde #6 : 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
|
|
|
Memorat
|
|
|
|
•Marius
|
|
« Răspunde #7 : 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! 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.
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
u-92
Vizitator
|
|
« Răspunde #8 : 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!
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #9 : Februarie 16, 2006, 09:16:43 » |
|
Ce nu e clar la solutia oficiala?
|
|
|
Memorat
|
|
|
|
•hitmann
Strain
Karma: 2
Deconectat
Mesaje: 14
|
|
« Răspunde #10 : Februarie 16, 2006, 22:57:17 » |
|
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 )
|
|
|
Memorat
|
|
|
|
VladS
Vizitator
|
|
« Răspunde #11 : 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: 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
|
|
|
Memorat
|
|
|
|
•bogdan2412
|
|
« Răspunde #12 : 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 .... 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
|
|
|
Memorat
|
|
|
|
•gabitzish1
|
|
« Răspunde #13 : 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
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #14 : Martie 29, 2007, 21:18:32 » |
|
Test: 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:
|
|
|
Memorat
|
Am zis
|
|
|
•gabitzish1
|
|
« Răspunde #15 : 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 :
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #16 : Martie 30, 2007, 13:05:32 » |
|
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
Nu e foarte greu sa faci un generator si un brute la problema asta. Ai putea incerca sa ti-o testezi singur.
|
|
|
Memorat
|
Am zis
|
|
|
•Florian
|
|
« Răspunde #17 : Martie 05, 2009, 14:25:27 » |
|
Ar putea cineva binevoitor sa dezvolte putin paragraful asta din articolul cu solutii ? 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!
|
|
« Ultima modificare: Martie 05, 2009, 14:28:05 de către Paul-Dan Baltescu »
|
Memorat
|
|
|
|
•gabitzish1
|
|
« Răspunde #18 : 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].
|
|
|
Memorat
|
|
|
|
|