Supponiamo di avere una collezione di blocchi, ognuno con una certa altezza e un certo peso. Ad esempio:
Sample input:
(190, 190) (120, 40) (100, 10) (90,130) (70, 40) (60, 70) (30, 30) (10, 90)
Sample output:
4
Vuoi trovare il numero massimo di blocchi che puoi accumulare, con 2 vincoli: ogni blocco deve essere più leggero di quello sottostante e deve anche essere più corto di quello sottostante. Come lo risolvi?
Il mio approccio era di risolverlo più o meno come il problema dello zaino. Ordino i blocchi dalla luce a quelli più pesanti e inizio alla fine dell'array. Quindi, per ogni blocco che sto considerando, trovo il massimo tra l'accumulare quel blocco e non accumularlo, e restituirlo. Ecco il codice C:
int maxPile(Blocks array[], int block, int maxHeight, int maxWeight){
/* base case with just 1 block left to consider */
if (block==0){
if ((array[0].height < maxHeight) && (array[0].weight < maxWeight))
return 1;
else
return 0;
}
/*case where current block can be piled, check the max between piling or not*/
if ((array[block].height < maxHeight) && (array[block].weight < maxWeight))
return max(1+maxPile(array,blockk-1,array[block].height,array[block].weight),maxPile(array,block-1,maxHeight,maxWeight));
/*case where current block can't be piled, so move to next*/
else
return maxPile(array,block-1,maxHeight,maxWeight);
}
L'algoritmo di cui sopra sembra risolvere il problema correttamente. Il problema, come avrai intuito, sono i sottosistemi sovrapposti, quindi la complessità è esponenziale.
Il modo usuale per risolvere questo problema è la programmazione dinamica, ma sto avendo difficoltà a implementarlo, in particolare a causa dei 2 vincoli.
Se esistesse un unico vincolo, ad esempio peso, creerei un array bidimensionale in cui le righe rappresenterebbero il sottoinsieme di blocchi con cui si sta lavorando e le colonne rappresenterebbero il peso massimo disponibile.
Ma con 2 vincoli avrei bisogno di avere una matrice tridimensionale per archiviare le soluzioni dei sottoproblemi, e non appena il set di dati cresce un po 'diventa irrealizzabile.
Un'altra idea che ho considerato è stata quella di prendere i 3 fattori (blocco corrente, peso massimo e altezza massima), passarli attraverso una funzione di hash e memorizzare il risultato in una tabella hash. Per qualche motivo questo non funziona.
Qualche idea su come aggiungere la programmazione dinamica alla soluzione di cui sopra? (o su come risolverlo in modo più efficiente?).
Aggiornamento : sembra che sia anche necessario ordinare l'array secondo il secondo vincolo (es. altezza in questo caso) ed eseguire nuovamente la funzione, poiché con questo ordine il massimo potrebbe essere maggiore.
