Olimpo Informatico

[ulisse]

Se non volete perdervi nell'ambientazione di fantasia andate a leggere il quesito puro in fondo al post.


Chi ha avuto la sfortuna di lavorare (a me successe qualche anno fa) sa che nelle aziende vige il principio di Dilbert: non è la competenza a pagare e quindi fa più carriera chi è più incompetente (o chi è bravo a fingere di esserlo).

Ecco pertanto che il nostro magazziniere, essendo stato tacciato di incompetenza, viene promosso responsabile di un nuovo ufficio appositamente inserito in organigramma per lui: l'ufficio pianificazione carichi.

Il suo compito è quello di determinare le misure minime dei furgoni che verranno inviati a ritirare la merce.

"Ciò", leggo dall'ordine di servizio, "al fine di garantire la massima qualità ai nostri clienti fornendo loro non solo i migliori prodotti a prezzi contenuti ma garantendo loro tutta la nostra attenzione per i loro profitti secondo il principio che un centrimetro cubo di spazio risparmiato è un centimetro cubo di spazio guadagnato!"

Ma non voglio divagare ulteriormente.

Poiché il magazziniere è stato nominato responsabile, la sua retribuzione viene legata alle sue prestazioni.
La paga base sarà moltiplicata per un coefficiente ottenuto mettendo a rapporto due misure.
A denominatore c'è la misura k del lato del più piccolo quadrato in cui l'ex magazziniere riesce a infilare gli scatoloni.
A numeratore c'è il più piccolo intero h il cui quadrato supera il numero degli scatoloni da consegnare.

Ad esempio con n=5 scatoloni (di dimensione 1x1x1) da consegnare, il numeratore è h = 3 e il miglior denominatore che siamo stati in grado di trovare è k = 2 + RAD(2)/2

Se il magazziniere fosse stato già promosso, avrebbe incrementato la sua paga base di un fattore h/k pari a circa 1,108194+ (il + indica l'arrotondamendo per difetto ovvero il valore reale è + grande)

Qual è il miglior k che siete in grado di suggerire al nostro ex magazziniere nel caso debba consegnare n = 11 scatoloni?
E nel caso n = 19 ?

Ecco il quesito in forma "pura":
Determinare il lato k del più piccolo quadrato nel quale inserire senza sovrapposizioni n quadrati di lato unitario.

[Salmastro]

...mi ricorda tanto il problema che hanno gli statunitensi quando un nuovo stato entra a far parte dell'Unione e devono disporre le stelle sulla bandiera...
ci penso
ciao
salmastro

[Taifu]

[Salmastro]

una soluzione efficiente mi riesce solo nel caso di un numero di scatole (S) pari a (n^2+1), dove n è uguale a h-1
per intenderci se h=3, S=5; se h=4, S=10 (con 11 ho grooossi problemi);
se h=5, S=17 (con 19...).
in sostanza

[ulisse]

Ottimo ragionamento!
Con un numero di scatole S = n^2 + 1 la migliore configurazione conosciuta è proprio quella.

Per S = 5 è anche dimostrato essere la migliore.
Negli altri casi non è stato dimostrato ma nessuno è riuscito a fare di meglio.



I casi n = 11,17,18,19 hanno delle soluzioni di questo tipo (scatoloni uno accanto all'altro in disposizione regolare tranne uno o più scatoloni ruotati di 45° per riuscire a infilarli nella zona centrale).

Ma nei casi n = 11,18,19 esistono soluzioni ancora più spinte che abbattono ulteriormente il rapporto h/k sfruttando sia disposizioni irregolari sia rotazioni diverse da 45°

@Taifu: non posso negare di aver pensato a te chiedendomi "come farà a delegare al pc tutto il lavoro sporco?"