PD[algorimi]

[Giova411]

Ragazzi volevo modificare quest'esercizio classico:
/* tolto link poiché l'esercizio è diverso (come notato dai moderatori), vedasi quindi immagine post successivi */

La modifica è di non metterne una sull'altra ma una all'interno dell'altra senza mai poterle girare.
Ossia vengono date le misure AxLxP e tali rimangono (non possiamo ruotarle per farle entrare in modalità diverse).

Vogliamo avere il massimo numero possibile che sia "racchiuso" una dentro l'altra (le altre verranno scartate e non ci interessano).

Ovviamente una entra nell'altra se (e solo se!) ha sia A che L e P minore di quella che la conterrà.

Esempio:
se ho le seguenti misure:
------------------
1x1x1
2x2x2
1x1x2
3x3x3
1x2x3
2x1x2
------------------
Possiamo dire che il risultato è 3 perché 1x1x1 entra in 2x2x2 che entra in 3x3x3. Altre non ce ne sono.

Ecco io non so farlo e ci sto pensando da poco.

Ho pensato che si potrebbe iniziare con la più piccola (la prima del conteggio) e chiuderla nella più grande, ma più piccola possibile delle rimanenti (esclusa la prima)... Così via. E' un problema dello zaino o sbaglio? Si può risolvere in O(n*n)? E' inteso che bisogna ordinare per volume calcolando per ciascuno a·b·h... Poi la misura dello zaino cambia in base all'ultimo volume disponibile. Ma si può scendere a O(nlogn) ?
Però, se ragiono coi volumi, il discorso che il risultato dell'esempio risulti 3 non andrebbe bene!!!!

[Giova411]

Ragazzi devo abbandonare l'idea di risolverlo così (come lo pseudocodice di cui sopra)? O qualcosa di giusto c'è?
Come dice Apa, quindi diversamente, mi pare fattibile

[Giova411]

Ragazzi avete poi, "per caso" , risolto l'esercizio?
Dico una versione perfetta come suggeriva Apa?

io...