Salve,

ultimamente sto cercando di risolvere il seguente problema di ottimizzazione:

suddividere un piano (un rettangolo o quadrato) con degli oggetti con superfici definite (es. altri quadrati e/o rettangoli).


Ho studiato vari algoritmi di ottimizzazione ma non sono riuscito ad oggi a trovarne qualcuno ottimale.

Ho provato a studiare il problema dello zaino (finito) ma comunque non risolve il problema.

Ho provato anche con qualche algoritmo di programmazione dinamica e sono riuscito a trovare delle soluzioni ma non ottimali (che non considerano i sottoinsiemi come oggetti unici).

Ad esempio vorrei risolvere un caso del genere:

dividere un piano 5 x 5 (area 25) con i seguenti oggetti:

oggetto a: 3 x 3 (area 9)
oggetto b: 2 x 2 (area 4)

Con alcuni algoritmi ho avuto il seguente risultato:

n.1 oggetto a
n.4 oggetti b

Scarto area 0

Ma il risultato che vorrei ottenere è

n.1 oggetto a
n.3 oggetti b

Scarto area 4 (in quanto non è possibile inserire un altro oggetto b nel piano).

Vi ringrazio per l'aiuto.