XspeedIt est une société d'import / export ayant robotisé toute sa chaîne d'emballage de colis.
Elle souhaite trouver un algorithme permettant à ses robots d'optimiser le nombre de cartons d'emballage utilisés.
Les articles à emballer sont de taille variable, représentée par un entier compris entre 1 et 9.
Chaque carton a une capacité de contenance de 10.
Ainsi, un carton peut par exemple contenir un article de taille 3, un article de taille 1, et un article de taille 6.
La chaîne d'articles à emballer est représentée par une suite de chiffres, chacun représentant un article par sa taille.
Après traitement par le robot d'emballage, la chaîne est séparée par des "/" pour représenter les articles contenus dans un carton.
Exemple
Chaîne d'articles en entrée : 163841689525773
Chaîne d'articles emballés : 163/8/41/6/8/9/52/5/7/73
L'algorithme actuel du robot d'emballage est très basique.
Il prend les articles les uns après les autres, et les mets dans un carton.
Si la taille totale dépasse la contenance du carton, le robot met l'article dans le carton suivant.
Implémenter un algorithme qui permettrait de maximiser le nombre d'articles par carton, en utilisant un langage pouvant être exécuté sur une JVM 1.7 minimum ou en node.js.
L'ordre des cartons et des articles n'a pas d'importance.
Exemple
Articles : 163841689525773
Robot actuel : 163/8/41/6/8/9/52/5/7/73 => 10 cartons utilisés
Robot optimisé: 163/82/46/19/8/55/73/7 => 8 cartons utilisés
L'idée est de créer un module qui est performant et facile à utiliser.
Ce programme a la complexité en temps O(n) et complexité en space en O(1).
node version 7.10
node app.js 163841689525773
Exemple de sortie:
Articles: 163841689525773
Robot optimisé: 91/82/81/73/73/64/6/55
Ou require('src/robot') et utiliser la fonction pack.
En introduisant un map, on évite de faire un triage d'articles qui est en nlog(n). Le map permet aussi de itérer l'entièrement les données en limité à 10 itération.
- Regrouper les articles en poids, avec un map/tableau comme:
{poids: nombre d'articles}
. - Itérer sur ce tableau, pour chaque poids, chercher les poids à compléter un carton(en trouvant les poids max disponibles). Quand un poids est choisit, décrémente le nombre d'articles pour ce poids.