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]

Io il codice lo posto, ma non sono convinto che funzioni in ogni caso.....

#include <iostream>
#include <algorithm>
using namespace std;

struct box{
  int h, w, d;   // height h, width w e depth d  
};

bool compare (box a, box b){
  int vola = (a.h * a.w * a.d) ;  
  int volb = (b.h * b.w * b.d) ;  
  return ( (vola <= volb)  );
}

int conta(box a[], int n) {
if (n==0) return 0;

  box boxes[n];  
  int somma = 1; // una scatola sicuro ci sarà
  int index = 0;

  for (int i = 0; i < n; i++){
      boxes[index] = a[i];
      index++;
   }
 int ans[n];
 sort (boxes, boxes + n, compare);
 int j;

for (int i = 0; i < n; i++){ 
      j=0;
      while (j < n){
         if (boxes[i].w < boxes[j].w  &&  boxes[i].d < boxes[j].d  &&  boxes[i].h < boxes[j].h ){                        
             somma = somma + 1;
             i = j;
          }
        j++; 
       }
    }
  return somma;
}

int
main (void){
  box a[] = { {1,1,1}, {2,2,2}, {1,1,2}, {3,3,3}, {1,2,3}, {2,1,2} };	
  int n = sizeof (a) / sizeof (a[0]);
  cout << "Numero massimo: " << conta(a, n) <<endl;
  return 0;
}

Con quali misure in input potrebbe fallire questo codice?

[apatriarca]

Non sono convinto che il problema sia in questo caso ben definito. Che cosa significa esattamente "Vogliamo avere il massimo numero possibile che sia "racchiuso" una dentro l'altra (le altre verranno scartate e non ci interessano)." Conta quindi solo il numero?

[Giova411]

Si il numero massimo APa, quindi il punto 1 seguente:

Bnotte <--- ma che fa?! Sbadiglia o s'incazz??

[vict85]

Quindi è una variante della longest incresing subsequence in cui sostituisci l'ordine totale con un ordine parziale. Tutto sommato conviene ignorare le scatole pensare di essere in \(\mathbb{R}^3\) dato che le scatole si possono ruotare e affiancare.

Per risolverlo basta quindi prendere un algoritmo per quel problema e chiedersi se è adatto ad essere usato con ordini parziali e nel caso come va modificato, sempre che sia possibile farlo.

[Giova411]

Non si possono ruotare e vanno inserite una nell'altra e si vuole il numero massimo possibile.
A me viene il Greedy con pre-elaborazione, ma non so bene se ordinare per volume sia una cosa buona e giusta...

[Giova411]

Buongiorno ragazzi!
Non mi lasciate nel limbo =)
E' giusto come ho ragionato?

[Giova411]

Allora è sbagliato il mio codice perché NON si può ordinare (in alcun modo!) e bisogna stampare le scatole che si scelgono.
Mi sembrava troppo "banale" la mia soluzione....

quindi dovrebbe tornare:

1x1x1
2x2x2
3x3x3

[JackMek]

Spero di aver capito bene l'esercizio.
Mi sembra che usando l'algoritmo LIS,come indicato da vict85,cambiando naturalmente il confronto con quello voluto dal testo,dovresti riuscire.

Ti scrivo una implementazione in python

Codice LIS copiato pari pari(lo trovi anche implementato in C)
A parte il confronto che non è più tra due valori, ma tra 2 liste

def Scat(array):
    n = len(array)
    q = [0] * n
    p = [-1] * n
    for i in range(n):
        maxLen = 0
        for j in range(i):
            if confronto(array[i],array[j]): 
                if q[j] > maxLen:
                    maxLen = q[j]
                    p[i] = j
        q[i] = maxLen+1
    idx = q.index(max(q))
    seq = []
    while(idx != -1):
        seq = [array[idx]] + seq
        idx = p[idx]
    return seq

Codice confronto

def confronto(a,b):
    if a[0] > b[0] and a[1] > b[1] and a[2] > b[2]:
        return True
    return False

Chiamata

Scat([[1,1,1],[2,2,2],[1,1,2],[3,3,3],[1,2,3],[2,1,3]])

Risultato

[[1, 1, 1], [2, 2, 2], [3, 3, 3]]

[Giova411]

Ti ha mandato APA???? Per il Python dico... Grazie per la partecipazione Jack!!

Io, al momento, ho trovato il numero ma devo stampare per bene le box.
Codice diverso dal tuo, guarda se ti va
Però devo correggerlo......

struct box
{
  int h;
  int l;
  int w;
};
typedef struct box box;

void solve (box temp[], int n){
  int i=0;
  int j=0;
  int idx = 0;    
  int N[n];
  int prev[n];
  prev[0] = 0;

  for (i = 0; i < n+1; i++)    {
      j = i - 1;
      while (j > 0  && !(temp[j].l < temp[i].l && temp[j].w < temp[i].w && temp[j].h < temp[i].h)){
        //cout << j << endl;
	j = j - 1;
	
      }
      prev[i] = j;
    }

 for (int ii = 0; ii < n; ii++)
    //cout <<prev[ii]<< endl;
 N[0] = 0;
  for (i = 0; i < n; i++){
    N[i] = max (N[i - 1], N[prev[i]]+1);  // N[i] massimo numero di scatole
  }

 for (int ii = 0; ii < n; ii++)
    cout <<N[ii]<< endl;
  i = n-1; 
  while (i > 0){
   if (N[i] != N[i - 1]){
	cout << temp[i].h<<"x"<<temp[i].l<<"x"<<temp[i].w << endl;
	i = prev[i];
      }
    else
      i = i - 1; 
  }
 cout << temp[i].h<<"x"<<temp[i].l<<"x"<<temp[i].w << endl;
  

}

int
main (void){

  box temp[] = {
    {5, 5, 5},
    {4, 4, 4},
    {3, 3, 3}, 
    {2, 2, 2},    
    {1, 1, 1},    
     };
  int n = sizeof (temp) / sizeof (temp[0]);
  solve (temp, n);
  return 0;
}

[Giova411]

Però il mio, con questo input, sbaglia....

  box temp[] = {
    {1, 1, 1},
    {4, 5, 6},
    {2, 2, 2},
    {1, 1, 2},
    {3, 3, 3},
    {1, 2, 3},
    {2, 1, 2},
    {4, 5, 6},
    {7, 7, 7},
  };
  

[vict85]

La mia era una ipotesi, non una risposta. Alcuni algoritmi per il LIS funzionano solo con ordini completi, ma con gli ordini parziali alcuni elementi non sono confrontabili. Graficamente le relazioni sono dei grafi disconnessi. Un algoritmo quindi come quello che usa il Longest common subsequence semplicemente non può funzionare. A meno di lavorare su questo insieme di grafi disconnessi oppure si potrebbe usare il fatto che cambiando l'ordine lessicografico questi elementi rimangono nello stesso ordine. Ma sono ipotesi, bisognerebbe dimostrarlo. Immagino si possa usare un metodo di programmazione dinamica.

[Giova411]

"vict85":Immagino si possa usare un metodo di programmazione dinamica.

Sì e stavo cercando di trovarlo... Però è un po' un esercizio ambiguo direi

@Jack: sicuro che funziona il tuo? L'hai testato?

[JackMek]

Se ho capito l'esercizio io non vedo problemi sinceramente.
Ho testato il codice e mi sembra che dia sempre un valore corretto.
Ma non sono molto bravo, quindi, quasi certamente, c'è qualche errore che non vedo...


Di C++ non so nulla, quindi non posso aiutarti da quel lato.
Ne ho scritta una implementazione in C(per quel poco che ricordo) che stampa la lunghezza massima(non le scatole)
Per trovare anche le scatole si potrebbero salvare le coppie valide
e successivamente trovare la sequenza da queste coppie(ultimo elemento uguale al primo...)
Ma è evidente che sia un metodo pessimo e ci sono sicuramente soluzioni migliori...

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

typedef struct{
    int x,y,z;
}box;

int confronta(box a, box b){
    if ( (a.x > b.x) && (a.y > b.y) && (a.z > b.z) ){
        return 1;
    }
    return 0;
};

int lis( box *a, int N ) {
   int *best, i, j, max = INT_MIN;
   best = (int*) malloc ( sizeof( int ) * N );
 
   for ( i = 0; i < N; i++ ) best[i] = 1;
 
   for ( i = 1; i < N; i++ )
      for ( j = 0; j < i; j++ )
         if (confronta(a[i],a[j]) && best[i] < best[j] + 1 ){
		    best[i] = best[j] + 1;
			if(max < best[i])
				max = best[i];
		 }         
 
   free(best);
   return max;
}
int main(){
  box b[] = {
    {1, 1, 1},
    {4, 5, 6},
    {2, 2, 2},
    {1, 1, 2},
    {3, 3, 3},
    {1, 2, 3},
    {2, 1, 2},
    {4, 5, 6},
    {7, 7, 7},
  };
  printf("%d\n", lis( b, sizeof(b)/sizeof(b[0]) ) );
}

Spero ti possa comunque essere utile.

[vict85]

Provata a fare i calcoli con

{{1,5,20}, {2,6,21}, {3, 7, 22}, {15, 1, 5}, {16,2,6}, {5, 52, 1}, {6, 53, 2}, {7, 54, 3}, {8, 55, 4}}  

dovrebbe venire 4. Si noti che l'insieme è formato da 3 catene indipendenti e scritte in modo ordinato.
e anche con

{ {1,1,1}, {2,2,2}, {3, 3, 3}, {4, 25, 4}, {25,4,4}, {4, 4, 25}, {26, 5, 5}, {5, 5, 26}, {27, 6, 27} }  

dovrebbe venire 6. Se non ho fatto calcoli errati.

EDIT: Ok, ho sia testato questi casi che guardato il codice ed in effetti non è influenzato dalla presenza di elementi non confrontabili.

[Giova411]

Sì pare che Jack abbia scritto la soluzione esatta.

L'equazione di ricorrenza potrebbe essere questa partendo da una box iniziale (0x0x0).
$ \S_i < S_j $ significa che entra soddisfando le tre misure minori && && &&.
Poi si valuta se NON PRENDO la box o se PRENDO la box

Caso base: $ \return -> 0 $ se $ \ j=0 $

$ \ N[j] = max{( N[j-1], (N[max{i: 0<= i < j $ $ \&&$ $ \ S_i < S_j}]) + 1 ) }$ se $ \ j>0$

Per stamparle in ordine poi, almeno per me, diventa

Vorrei riuscirle a stampare, seguendo l'ultimo test di Vic, così:

1x1x1
2x2x2
3x3x3
4x25x4
26x5x5
27x6x27

..

 j = N-1;

 while (j>0){
  if (best[j] != best[j-1]) {
   printf ("%dx%dx%d\n", a[j].x, a[j].y, a[j].z );
    j= j-1; // qui è l'errore!
  }else
    j=j-1;
 } 

printf ("%dx%dx%d\n", a[j].x, a[j].y, a[j].z );
..

Che dite? (sono pessimo!!! )

[apatriarca]

[ot]Il grafo di una relazione d'ordine parziale non è disconnesso. Semplicemente non è completo come nel caso di un ordine completo. Un esempio possono essere i punti con coordinate intere nel primo quadrante (con ordine dato in modo simile a questo esercizio). Il grafo in questo caso è un albero (o un albero con tutti gli archi al contrario a seconda di come si definisce la relazione e gli archi).[/ot]

[Giova411]

Apa quando fai così non sempre ti seguo (il NON SEMPRE è per esagerare a mio favore!)

Apritemi la testa che sono IDIIIOOOOOT................
Vorrei stampare pure le boxes ma UN CE LA SI FO (dando per buono il codice di JACK)

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
typedef struct
{
  int x, y, z;
} box;

int
confronta (box a, box b)
{
  if ((a.x > b.x) && (a.y > b.y) && (a.z > b.z))
    {
      return 1;
    }
  return 0;
};

int
lis (box * a, int N)
{
  int *best, i, j, max = INT_MIN;
  best = (int *) malloc (sizeof (int) * N);

  int prec[N];

  for (i = 0; i < N; i++)
    best[i] = 1;

  for (i = 1; i < N; i++){
    for (j = 0; j < i; j++){     
      if (confronta (a[i], a[j]) && best[i] < best[j] + 1)
	{
 	  prec[i] = j;
          //printf ("%d\n", j );
	  best[i] = best[j] + 1;
         
	  if (max < best[i])
	    max = best[i];   
            
	}      
      }
    
   }

  // for (j = 0; j < N; j++)
   //  printf ("%d\n",prec[j]);

 j = N-1;

 while (j>0){
  if (best[j] != best[j-1]) {
   printf ("%dx%dx%d\n", a[j].x, a[j].y, a[j].z );
     j= prec[j];
  }else
    j=j-1;
 
 } 

printf ("%dx%dx%d\n", a[j].x, a[j].y, a[j].z );
  free (best);
  return max;
}

int
main (void)
{
  box b[] = {
    {1, 1, 1}, {2, 2, 2}, {3, 3, 3}, {4, 25, 4}, {25, 4, 4}, {4, 4, 25}, {26, 5, 5}, {5, 5, 26}, {2, 2, 2}, {27, 6, 27}};
  printf ("%d\n", lis (b, sizeof (b) / sizeof (b[0])));
return 0;
}

Anche se al contrario pare stamparle...
Ma se cambio output non riesco a seguire "il conto" (si rompe quella sorta di "albero" )
Non va con questo:

{ {1, 1, 1}, {2, 2, 2}, {3, 3, 3}, {4, 25, 4}, {25, 4, 4}, {4, 4, 25}, {26, 5, 5}, {5, 5, 26}, {2, 2, 2}, {27, 6, 27}, {3, 3, 3}};

Peggio con questo:

{ {1, 1, 1}, {2, 2, 2}, {3, 3, 3}, {4, 25, 4}, {25, 4, 4}, {4, 4, 25}, {26, 5, 5}, {5, 5, 26}, {2, 2, 2}, {27, 6, 27}, {1, 1, 1}};

[apatriarca]

@Giova: si trattava semplicemente di una piccola digressione teorica in risposta principalmente a Vittorio. Non era una proposta di soluzione.. In effetti non ho pensato seriamente alla soluzione.

[apatriarca]

In realtà a me il tuo programma non funziona neppure per l'input iniziale. E devo dire che non capisco il senso del ciclo finale in cui stampi i valori. Perché confronti best[ j ] con best[ j - 1 ]? Non avrebbe a questo punto più senso memorizzare l'indice i per cui best[ i ] = max e quindi andare indietro con le relazioni a partire da quella? Oltretutto non mi sembra che prec sia stato inizializzato..

Volendo a questo punto discutere dell'algoritmo.. Siete sicuri che sia corretto? Se considero infatti i box {{3,3,3},{1,1,1}} in questo ordine, best[0] = best[1] = 1 alla fine del ciclo e non credo sia quello che si desidera ottenere.

Perché sia corretto i valori dovrebbero a mio parere essere "ordinati" usando una relazione d'ordine totale. Un esempio è l'ordine lessicografico (anche se per molte applicazioni altri ordini sono preferibili). In alternativa è in realtà possibile anche ordinare in base al grado. Siccome \( (a, b, c) \prec (\alpha, \beta, \gamma) \) se \( a < \alpha \wedge b < \beta \wedge c < \gamma \) avremo che
\[ (a, b, c) \prec (\alpha, \beta, \gamma) \implies (\alpha + \beta + \gamma) - (a + b + c) \geq 3. \]
La dimostrazione è molto semplice. Questo significa comunque che se le triplette sono ordinate in base al grado, tutte le triplette che possono essere in essa contenute la precedono.

In alternativa all'ordinamento si può aggiungere un ciclo. Si calcola prima best della tripletta corrente basandosi sulle triplette che la precedono nell'array e si aggiornano poi gli eventuali valori di best delle triplette che la precedono nell'array ma che potrebbero contenerla.

[Giova411]

"apatriarca":\[ (a, b, c) \prec (\alpha, \beta, \gamma) \implies (\alpha + \beta + \gamma) - (a + b + c) \geq 3. \]

E questa dove l'hai trovata?!?!?!??! Mitico


Lo pseudocodice proposto come soluzione all'esercizio lo riporto ma

Non va con me. $O(n^2)$