133 Zebughil

[ditzone]

Aici puteţi discuta despre problema Zebughil.

[•Marius]

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.

[VladS]

E cumva Multiple Knapsack Problem ?

[•Cosmin]

Da, e.

[•hitmann]

?! 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?)

[u-92]

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

[•hitmann]

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

[•Marius]

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.

[u-92]

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

[•Cosmin]

Ce nu e clar la solutia oficiala?

[•hitmann]

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 )

[VladS]

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

[•bogdan2412]

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

[•gabitzish1]

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

[•pauldb]

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

[•gabitzish1]

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 :

[•pauldb]

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.

[•Florian]

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!

[•gabitzish1]

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].