Bonjour,
Il faut d'abord constituer le tableau (T
0) d'enregistrements, dont chacun caractérise un objet par son poids, son volume, ainsi que le rang de la boîte dans laquelle il sera rangé (cet indice étant initialement nul).
De ce tableau peuvent être déduits deux autres, dans lesquels les objets sont classés selon l'ordre décroissant de leur poids (T
P) ou de leur volume (T
V).
On remplit ensuite la première boîte jusqu'à l'épuisement des choix en prenant systématiquement:
- soit
l'objet de volume maximal compatible avec le volume encore disponible (V
i < V'
1), et de poids inférieur à la limite correspondante (P
i < P'
1), en travaillant sur le tableau (T
V);
- soit
l'objet de poids maximal compatible avec le poids encore disponible (P
i < P'
1), et de volume inférieur à la limite correspondante (V
i < P'
1, en travaillant sur le tableau (T
P);
- soit encore
l'objet présentant le meilleur taux de remplissage g = (V
i/V'
1) + (P
i/P'
1) calculable sur le tableau initial (T
0), l'objet vérifiant toujours les mêmes conditions:
(Vi < V'1) et (Pi < P'1) .
On affecte la valeur (1) à l'indice (n) des objets ainsi sélectionnés.
On remplit de même la seconde boîte à l'aide des objets restants, (n) passant désormais de (0) à (2), puis à la troisième et ainsi de suite jusqu'au rangement complet.
Le procédé est arbitraire, mais conduit intuitivement à un arrangement suffisamment compact pour être acceptable; ses trois variantes permettent d'ailleurs la comparaison des nombres de colis constitués.
Et rien n'interdit de voir ce que donnerait le fait d'opérer selon l'ordre croissant des valeurs considérées (procédé probablement moins efficace).
À titre de comparaison, on peut considérer:
- le nombre maximal de boîtes, égal au nombre total d'objets (N
tot);
- les valeurs moyennes du nombre de boîtes déductibles de celles du poids et du volume des objets;
NV = V/VB = (Vtot/Ntot)/VB ;
NP = P/PB = (Ptot/Ntot)/PB ;
- le nombre minimal de colis, qui est celui des objets dépassant simultanément la moitié des deux limites permises, et vérifiant:
Vi > VB/2 et Pi > PB/2 .
Partager